HDU 2444 The Accomodation of Students 判断是否为二分图，二分图的最大匹配

题意：问给出的图是不是二分图，如果是输出最大匹配，不是输出"No"。

可以利用BFS对图染色来判断一个图是否为二分图。

首先图上各节点为无色的，任选一个未染色节点将其染上红色，然后以该点为原点进行BFS。

从队列中取出点P，若P为红色，则将与其直接相连的点染上蓝色，否则染上红色。若与P直接

相连的点已染色且与P颜色相同，则此图存在奇回路，即不是二分图，BFS终止。

若直到所有点均被染上色且未触发终止条件，则说明此图为二分图。

二分图的最大匹配。

定义：给出一个二分图，找到一个边数最大的匹配，即尽量多的边，使得任意两条选中的边没有公共点。

增广路算法。

增广路定义：终点和起点（两点不相同）均为未盖点（未匹配的点）且 只有这两个点为未盖点  且 路上的已盖点的数量不为奇数 的路称为增广路。

算法描述：

每次选择一个新的未盖点为起点寻找增广路，若找到则匹配数加一，若找到则路上的所有点均标记为已匹配点。

寻找过程：从一个未盖点开始，若与其直接相连的点中有未盖点则找到一条增广路，寻找结束。

    若没有则选择一个已盖点A，然后选择与A匹配的点B，若与B直接相连的点中有未盖点，则找到一条增广路，寻找结束。

    若没有，则选择一个新的已盖点作为A，A的匹配点为B，再从与B直接相连的点中寻找未盖点。

   以此类推，直到找不出新的A或找到了一个未盖点，前者表示没有找到一条增广路，后者反之。

下面说一下自己对增广路的理解：

因为增广路上的只有起点和终点为未盖点，且所有的点的个数为偶数，所以可以让第 i（i为奇数） 个点 与 第（i+1）个点匹配，这样就会多出一次匹配。

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>

#pragma comment(linker, "/STACK:1024000000");
#define LL long long int

using namespace std;

struct N
{
    int v;
    N *next;
}*head[200];

N *creat()
{
    N *p = (N *)malloc(sizeof(N));
    p->next = NULL;
    return p;
}

bool mark[210];

int color[210];

int Match_Point[210];

bool dfs(int t)
{
    for(N *p = head[t]->next; p != NULL; p = p->next)
    {
        if(mark[p->v] == false)
        {
            mark[p->v] = true;
            if(Match_Point[p->v] == -1 || dfs(Match_Point[p->v]))
            {
                Match_Point[p->v] = t;
                Match_Point[t] = p->v;
                return true;
            }
        }
    }
    return false;
}

bool bfs(int n)
{
    queue<int> q;
    int s,i;
    N *p;

    for(i = 1;i <= n; ++i)
    {
        if(color[i] == -1)
        {

            q.push(i);
            color[i] = 0;

            while(q.empty() == false)
            {
                s = q.front();
                q.pop();

                for(p = head[s]->next; p != NULL; p = p->next)
                {
                    if(color[p->v] == -1)
                    {
                        color[p->v] = (color[s] == 1 ? 0 : 1);
                        q.push(p->v);
                    }
                    else if(color[p->v] == color[s])
                    {
                        return true;
                    }
                }
            }
        }
    }

    return false;
}

int Cal_Maximal_Matching(int n)
{
    int i,ans = 0;

    memset(Match_Point,-1,sizeof(Match_Point));

    for(i = 1;i <= n; ++i)
    {
        if(Match_Point[i] == -1)
        {
            memset(mark,false,sizeof(mark));
            if(dfs(i))
                ans++;
        }
    }
    return ans;
}

int main()
{
    int i,n,m,u,v;
    N *p;

    for(i = 0;i <= 200 ; ++i)
    {
        head[i] = creat();
    }

    while(scanf("%d %d",&n,&m) != EOF)
    {
        for(i = 1;i <= n; ++i)
        {
            head[i]->next = NULL;
        }

        while(m--)
        {
            scanf("%d %d",&u,&v);
            p = creat();
            p->v = v;
            p->next = head[u]->next;
            head[u]->next = p;
            p = creat();
            p->v = u;
            p->next = head[v]->next;
            head[v]->next = p;
        }

        memset(color,-1,sizeof(color));

        if(bfs(n))//说明不是二分图
        {
            cout<<"No"<<endl;
        }
        else
        {
            printf("%d\n",Cal_Maximal_Matching(n));
        }
    }
    return 0;
}