题意：
有n个学生，他们之间可能互相认识。先判断是否可以分成两组，每组的学生互相都不认识，如果不能输出“No”。如果可以，每次从两组各拿出一个相互认识的学生组成一对，输出最多可以有多少对。
例如：
第一组数据：
4 4
1 2
1 3
1 4
2 3
由于1和其他所有学生都认识，而其它学生又有互相认识的，肯定不能分成两组了。
第二组数据：
6 5
1 2
1 3
1 4
2 5
3 6
可以分成下图的两组学生：
最多可找出(1,4)(5,2)(6,3)三对学生。
解题思路：
首先进行二分图的判断，用DFS即可。取任意点，标记(c)，搜索与其相连的点，如果该点没有被标记(0)，则将其标记为相反(-c)，继续向下搜索；如果被标记了，则判断其标记与应有的标记是否一致，一致则继续，不一致则可判断该图不是二分图。
第一组数据：
1 2 3 4
0 0 0 0
c 0 0 0
c -c 0 0
c -c c 0
此时回到点1的搜索，搜索到点3时发现其值为c，与点1的值相同，因此不是二分图。
第二组数据：
1 2 3 4 5 6
0 0 0 0 0 0
c 0 0 0 0 0
c -c 0 0 0 0
c -c 0 0 c 0
c -c -c 0 c 0
c -c -c 0 c c
c -c -c -c c c
搜索完成，中间没有任何冲突，因此是二分图。
然后用匈牙利算法计算二分图的最大匹配。
不熟悉匈牙利算法可以看这篇博客入门：http://blog.csdn.net/dark_scope/article/details/8880547
代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 #define MAX_V 205 7 using namespace std; 8 //保存点和点的分组 9 int G[MAX_V][MAX_V], lefts[MAX_V], rights[MAX_V]; 10 int V;//点数 11 int color[MAX_V];//各点的颜色 1或-1 12 int used[MAX_V], girl[MAX_V]; //是否使用过 匹配情况 13 bool dfs(int v, int c) 14 { 15 color[v] = c;//将该点染色 16 for(int i=0; i<V; i++) 17 { 18 if(G[v][i] == 1) 19 { 20 //该点相连的所有点都应为0或-c，否则不是二分图 21 if(color[i] == c) return 0; 22 //若未标记，则将其标记并向下搜索 23 if(color[i]==0 && !dfs(i, -c)) return 0; 24 } 25 } 26 return 1; 27 } 28 int finds(int x, int v2) 29 { 30 for(int j=0; j<v2; j++) 31 { 32 if(used[j] == 0) 33 if(G[lefts[x]][rights[j]] == 1) 34 { 35 used[j] = 1; 36 if(girl[j]==-1 || finds(girl[j], v2)==1) 37 { 38 girl[j] = x; 39 return 1; 40 } 41 } 42 } 43 return 0; 44 } 45 //判断是否是二分图 46 bool isBipartiteGraph(){ 47 //初始每个点都未标记 48 memset(color, 0, sizeof(color)); 49 for(int i=0; i<V; i++) 50 if(color[i] == 0) 51 if(!dfs(i, 1)) 52 return false; 53 return true; 54 } 55 //计算最大匹配 56 int calMaxMatch(){ 57 int v1=0, v2=0; 58 memset(girl, -1, sizeof(girl)); 59 memset(lefts, 0, sizeof(lefts)); 60 memset(rights, 0, sizeof(rights)); 61 for(int i=0; i<V; i++) 62 { 63 if(color[i] > 0) 64 lefts[v1++]=i; 65 else 66 rights[v2++]=i; 67 } 68 int ans = 0; 69 for(int i=0; i<v1; i++) 70 { 71 memset(used, 0, sizeof(used)); 72 if(finds(i, v2) == 1) 73 ans++; 74 } 75 return ans; 76 } 77 int main(void) 78 { 79 //freopen("2444.in","r",stdin); 80 int E; //边数 81 while(~scanf("%d%d",&V,&E)) 82 { 83 //如果只有一个点，则一定不是二分图 84 if(V==1) 85 { 86 printf("No "); 87 continue; 88 } 89 memset(G, 0, sizeof(G)); 90 for(int i=0; i<E; i++) 91 { 92 int s, t;//两个点 93 scanf("%d%d",&s,&t);//依次输入边的信息 94 G[s-1][t-1] = G[t-1][s-1] = 1; 95 } 96 if(isBipartiteGraph()) 97 printf("%d ",calMaxMatch()); 98 else 99 printf("No "); 100 } 101 return 0; 102 }
