hdu2444 二分图的匹配，先判断是否为二分图

http://acm.hdu.edu.cn/showproblem.php?pid=2444

4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6

No
3

/**
hdu2444 二分图的匹配，先判断是否为二分图
题目大意：给定一个图，判断是否为二分图如果是请求出最大匹配数
解题思路：对于是不是二分图:所有的点可以分到两部分，每一部分的点之间没有联系，我们可以用dfs搜索就知道了。
           至于二分图的匹配要用到匈牙利算法
*/
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
const int maxn=202;

vector <int>vec[maxn];
int linker[maxn];
bool used[maxn];
int n,m;
int matchs[maxn],cnt[maxn];

bool dfs(int u)
{
    for(int i=0;i<vec[u].size();i++)
    {
        int v=vec[u][i];
        if(!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int res=0;
    int u;
    memset(linker,-1,sizeof(linker));
    for(int u=1;u<=n;u++)
    {
        memset(used,false,sizeof(used));
        if(dfs(u))
            res++;
    }
    return res;
}

bool judge(int x,int y)
{
    int i;
    for(int i=0;i<vec[x].size();i++)
    {
        if(cnt[vec[x][i]]==0)
        {
            cnt[vec[x][i]]=y^1;
            matchs[vec[x][i]]=true;
            if(!judge(vec[x][i],y^1))return false;
        }
        else if(cnt[vec[x][i]]==y)
            return false;
    }
    return true;
}

bool matched()///判断是否为二分图
{
    memset(matchs,false,sizeof(matchs));
    for(int i=1;i<=n;i++)
    {
        if(vec[i].size()&&!matchs[i])
        {
            memset(cnt,0,sizeof(cnt));
            cnt[i]=1;
            matchs[i]=true;
            if(!judge(i,1))
                return false;
        }
    }
    return true;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        {
            if(vec[i].size())
                vec[i].clear();
        }
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        if(matched())
            printf("%d\n",hungary()/2);
        else
            printf("No\n");
    }
    return 0;
}

hdu2444 二分图的匹配，先判断是否为二分图

原文：http://blog.csdn.net/lvshubao1314/article/details/44056769