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 202using 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;}