hdu2444 判断二分图+最大匹配

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

#define maxn 210

int map[maxn][maxn],color[maxn];

int vis[maxn],match[maxn],n;

int bfs(int u,int n)

{

    int i;

    queue<int>q;

    q.push(u);

    color[u]=;

    while(!q.empty())

    {

        int v=q.front();

        q.pop();

        for(i=;i<=n;i++)

        {

            if(color[i]==-&&map[v][i])

            {

                q.push(i);

                color[i]=!color[v];

            }

            if(color[i]==color[v]&&map[v][i])

                return ;

        }

    }

    return ;

}

int dfs(int u)

{

    int i,j;

    for(i=;i<=n;i++)

    {

        if(map[u][i]&&!vis[i])

        {

            vis[i]=;

            if(match[i]==-||dfs(match[i]))

            {

                match[i]=u;

                return ;

            }

        }

    }

    return ;

}

int main()

{

    int i,j,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

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

        memset(map,,sizeof(map));

        memset(match,-,sizeof(match));

        for(i=;i<m;i++)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            map[x][y]=map[y][x]=;

        }

        int flag=;

        for(i=;i<=n;i++)

        {

            if(color[i]==-&&!bfs(i,n))

            {

                flag=;

                break;

            }

        }

        if(!flag)

        {

            printf("No\n");

            continue;

        }

        int ans=;

        for(i=;i<=n;i++)

        {

            memset(vis,,sizeof(vis));

            if(dfs(i))

                ans++;

        }

        printf("%d\n",ans/);

    }

}