hdu 2444 二分图判定+最大匹配

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

题目大意：有n个人之间有m对互相认识，问能否将所有人分成两组，同一组的任意两人互不认识。若不能分组输出“No”，若能分组计算并输出有最多有多少对人互相认识；

思路：先用DFS进行染色，判断能否分成两组组（即能否构成二分图），如果可以求二分图的最大匹配；

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 202
using namespace std;
int map[N][N],link[N],visit[N],color[N];
bool flag;
bool DFS(int i,int n,int c)
{
	int j;
	for(j=1;j<=n;j++){
		if(map[i][j]==1){
			if(color[j]==c)
				continue;
			if(color[j]==0){
				color[j]=c;
				flag=DFS(j,n,-c);
			}
			else{
				return false;
			}
			if(!flag)
				return false;
		}
	}
	return true;
}
bool find(int x,int n)
{
	int y;
	for(y=1;y<=n;y++){
		if(map[x][y]==1 && visit[y]==0){
			visit[y]=1;
			if(link[y]==-1 || find(link[y],n)){
				link[y]=x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	int n,m,a,b,i,cnt;
	while(scanf("%d%d",&n,&m)!=EOF){
		flag=true;
		memset(map,0,sizeof(map));
		memset(link,-1,sizeof(link));
		memset(color,0,sizeof(color));
		while(m--){
			scanf("%d%d",&a,&b);
			map[a][b]=map[b][a]=1;
		}
		for(i=1;i<=n;i++){//对每个点通过DFS进行染色
			if(color[i]==0)
				color[i]=1;
			flag=DFS(i,n,-color[i]);
			if(!flag)break;
		}
		if(!flag){
			printf("No\n");
			continue;
		}
		for(i=1,cnt=0;i<=n;i++){
			memset(visit,0,sizeof(visit));
			if(find(i,n))
				cnt++;
		}
		printf("%d\n",cnt/2);
	}
	return 0;
}