HDU2444 二分图

题意：

有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 }