二分图问题

二分图问题

1.染色法 判断是不是二分图 O(n+m)

//二分图当且仅当图中不含有奇数环(边数是奇数的环)
//for(i=1;i<=n;i++)
//	if (i未染色)  dfs(i,1)
int head[N],ne[2*N],e[2*N],idx;
int n,m;
int color[N];
void init()
{
    memset(head,-1,sizeof head);
    idx = 0;
}
void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = head[a];
    head[a] = idx ++;
}
bool dfs(int u,int c)
{
    color[u] = c;
    for(int i = head[u]; i != -1;i = ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j, 3 - c)) return false;
        }
        //产生矛盾：一条边上的两个点颜色相同
        else if(color[j] == c) return false;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    init();
    while(m --)
    {
        int a,b;
        cin>>a>>b;
        add(a,b); add(b,a);
    }
    bool flag = true;
    for(int i=1;i<=n;i++)
        if(!color[i]) 
        {
            if(!dfs(i,1))
            {
                flag = false;
                break;
            }
        }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}

2.匈牙利算法 实际运行时间非常少 O(mn),实际运行时间一般远小于O(mn) 这里的n是n个男孩

//返回二分图的最大匹配(要排除脚踩多条船的情况)
int n1,n2,m;
int head[N],e[M],ne[M],idx;
bool st[N];
int match[N];
void init()
{
    memset(head,-1,sizeof head);
    idx = 0;
}
void add(int a,int b)
{
    e[idx] = x; ne[idx] = head[a]; head[a] = idx ++;
}
bool find(int x)
{
    for(int i = head[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            if(match[j] == 0|| find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    cin>>n1>>n2>>m;
    init();
    while(m --)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    int res = 0;
    for(int i=1;i<=n1;i++)
    {
        memset(st,false,sizeof st);
        if(find(i)) res ++;
    }
    cout<<res<<endl;
    return 0;
}