二分図判定

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=2444
 
題意:無方向図を与え、まず二分図かどうかを判断し、もしそうであれば最大マッチングを求め、そうでなければ「No」を出力する.
二分図は、2つの頂点セットがあり、図中の各エッジの2つの頂点がそれぞれ2つの頂点セットに位置し、各頂点セットにはエッジが接続されていない図です.
二分図を判断する一般的な方法:いずれかの未染色の頂点を染色し始め、その後隣接する頂点を判断し、未染色であれば隣接する頂点とは異なる色に染め、すでに染色されていて色が隣接する頂点と同じであれば二分図ではないことを説明し、色が異なる場合は判断を続け、深さで探せばよい.無方向二分図のマッチングなので2で割る.

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 2005;

int head[N],link[N];
bool vis[N],col[N];
int cnt,n,m;

struct Edge
{
    int to;
    int next;
};

Edge edge[N*N];

void Init()
{
    cnt = 0;
    memset(head,-1,sizeof(head));
    memset(col,0,sizeof(col));
}

void add(int u,int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

bool Color(int u)
{
    for(int i=head[u]; ~i; i=edge[i].next)
    {
        int v = edge[i].to;
        if(!col[v])
        {
            col[v] = !col[u];
            if(!Color(v)) return false;
        }
        else if(col[v] == col[u])
            return false;
    }
    return true;
}

bool dfs(int u)
{
    for(int i=head[u]; ~i; i=edge[i].next)
    {
        int v = edge[i].to;
        if(!vis[v])
        {
            vis[v] = 1;
            if(link[v] == -1 || dfs(link[v]))
            {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

int match()
{
    int ans = 0;
    memset(link,-1,sizeof(link));
    for(int i=1; i<=n; i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ans++;
    }
    return ans;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n == 1)
        {
            puts("No");
            continue;
        }
        Init();
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        col[1] = 1;
        if(!Color(1))
        {
            puts("No");
            continue;
        }
        printf("%d
",match()>>1);
    }
    return 0;
}