（匹配）The Accomodation of Students --HDU --2444

链接：

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

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82834#problem/B

题意：

        有n个学生，有m对人是认识的，每一对认识的人能分到一间房，问能否把n个学生分成两部分，每部分内的学生互不认识，而两部分之间的学生认识。如果可以分成两部分，就算出房间最多需要多少间，否则就输出No。

朋友的朋友不是朋友，r代表他们之间的关系

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 205
#define INF 0x3f3f3f3f

struct node {int v, next;}e[N];

int n, m, p[N], used[N], Head[N], nx, bnt, f[N], r[N], G[N][N], x[N];

int FindFather(int x)
{
    int k = f[x];
    if(f[x]!=x)
    {
        f[x] = FindFather(f[x]);
        r[x] = (r[x] + r[k])%2;
    }
    return f[x];
}

int Find(int u)
{
    for(int i=1; i<=n; i++)
    {
        if(!used[i] && G[u][i])
        {
            used[i]=1;
            if(!p[i] || Find(p[i]))
            {
                p[i] = u;
                return true;
            }
        }
    }
    return false;
}


int main()
{
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        int i, ans=0, u, v;

        bnt = nx = 0;
        memset(G, 0, sizeof(G));
        memset(p, 0, sizeof(p));
        memset(used, 0, sizeof(used));
        memset(x, 0, sizeof(x));
        for(i=0; i<=n; i++)
        {
            f[i] = i;
            r[i] = 0;
        }

        for(i=1; i<=m; i++)
        {
            scanf("%d%d", &u, &v);
            G[u][v] = G[v][u] =1;

            int ru = FindFather(u);
            int rv = FindFather(v);

            if(ru==rv && r[u]==r[v])
                ans = 1;
            else if(ru!=rv)
            {
                f[ru] = rv;
                r[ru] = (r[u] + r[v] + 1) % 2;
            }
        }

        if(ans)
        printf("No
");
        else
        {
            for(i=1; i<=n; i++)
            {
                u = FindFather(i);
                if(r[i]==0)
                    x[nx++] = i;
            }

            int an=0;
            for(i=0; i<nx; i++)
            {
                memset(used, 0, sizeof(used));
                if(Find(x[i]))
                an++;
            }

            printf("%d
", an);
        }
    }
    return 0;
}