本文共 1670 字，大约阅读时间需要 5 分钟。

题意：给n个点和m条无向边，是否存在二分图，若存在，求最大匹配数，若不存在，输出"No"。

题解：染色法 匈牙利算法

1.染色法判断二分图：vis数组存储染的颜色，将所有点初始化为-1，dfs的方法若vis[i]为-1，则赋值为0，与第i个点相连的点都赋值为1-vis[i]。如果出现了相连的两点颜色相同的情况就不是二分图，反之是二分图。

2.匈牙利算法求最大匹配数的讲解和模板：

#include<stdio.h>#include<string.h>#include<algorithm>#include<vector>#include<math.h>using namespace std ;int n , m ;int vis[205] ;vector <int> color[205] ;bool used[205] ;int match[205] ;bool judge_dfs(int u) // 通过染色法判断是不是二分图 {    int i , j , k ;    int v ;	if(vis[u] == -1)	   vis[u] = 0 ;	for(i = 0 ; i < color[u].size() ; i ++)	{	   v = color[u][i] ;	   if(vis[v] == vis[u])	      return 0 ;	   if(vis[v] == -1)	   {	    	vis[v] = 1 - vis[u] ;	    	if(!judge_dfs(v)) 			   return 0 ;	   }		}	return 1 ;	    }bool find(int u) // 匈牙利算法模板 {  int i , j ;  int v ;  for(i = 0 ; i < color[u].size() ; i ++)  {  	v = color[u][i] ;    if(vis[v] == 1 && !used[v])	{		used[v] = 1 ;		if(match[v] == -1 || find(match[v]))		{			match[v] = u ;			return 1 ;		}	}	  }	  return 0 ;}int main(){  int i , j ;  int a , b ;  bool flag ;  int ans ;  while(scanf("%d%d" , &n , &m) != EOF)  {  	for(i = 1 ; i <= n ; i ++)        color[i].clear() ;    for(i = 0 ; i < m ; i ++)    {    	scanf("%d%d" , &a , &b) ;    	color[a].push_back(b) ;    	color[b].push_back(a) ;	}	memset(vis , -1 , sizeof(vis)) ;	flag = 1 ;	for(i = 1 ; i <= n ; i ++)	    if(vis[i] == -1 && !judge_dfs(i))	    {	    	flag = 0 ;		    break ;		}	if(!flag)	{	  printf("No\n") ;	  continue ;		}	ans = 0 ;	memset(match , -1 , sizeof(match)) ;	for(i = 1 ; i <= n ; i ++) // 匈牙利算法的主函数部分 	{	  if(vis[i] == 1)	     continue ;	  memset(used , 0 , sizeof(used)) ; // 记得每次初始化  	  if(find(i)) 	     ans ++ ;		}	printf("%d\n" , ans) ;	  }}