HDU 2444 The Accomodation of Students(Bipartite graph color)

Description

N个人M个相识关系，问：能否将所有人分成两拨，每一拨中的人彼此互不相识。若能，分成两拨后，能从彼此中挑出多少对相识的？

Analyze

1.判断是否是二分图（染色法）

2.二分图最大匹配

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20005;
const int M = 20005;

int n, m, color[N];;

int head[N], cnt;
struct edge
{
    int v, pre;
} e[M];

void add(int u, int v)
{
    e[cnt].v = v;
    e[cnt].pre = head[u];
    head[u] = cnt++;
}

bool succeed(int x)
{
    for(int i = head[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(color[to] == -1)
        {
            color[to] = 1 - color[x];
            if(!succeed(to))
                return 0;
        }
        else if(color[to] == color[x])
            return 0;
    }
    return 1;
}

bool vis[N];
int link[N];
bool DFS(int x)
{
    for(int i = head[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(!vis[to])
        {
            vis[to] = 1;
            if(link[to] == -1 || DFS(link[to]))
            {
                link[to] = x;
                return 1;
            }
        }
    }
    return 0;
}

void Match()
{
    int ans = 0;
    memset(link, -1, sizeof(link));
    for(int i = 1; i <= n; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if(color[i] == 0 && DFS(i))
            ans++;
    }
    cout << ans << '\n';
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        cnt = 0;
        memset(head, -1, sizeof(head));
        int u, v;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d", &u, &v);
            add(u, v), add(v, u);
        }

        bool flag = 0;
        memset(color, -1, sizeof(color));
        for(int i = 1; i <= n; ++i)
            if(color[i] == -1)
            {
                color[i] = 0;
                if(!succeed(i))
                {
                    cout << "No" << '\n';
                    flag = 1;
                    break;
                }
            }
        if(flag)
            continue;

        Match();
    }
    return 0;
}