题意： 有n个人，m对人相互认识； 问能否分成两个组，组内任意两个人之间不认识； 若不能，则输出 No； 若能，则相互认识的两个人一间房，求最多需要几间房；
给出一些学生的认识情况，比如A和B认识，B和C认识，但是A和C不一定认识。现在问能否将这些学生分成两个组，并且每组中的学生互相不认识，如果能分，求出最大能匹配的学生对数。
There are a group of students. Some of them may know each other, while others don’t. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other.
Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don’t know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room.
Calculate the maximum number of pairs that can be arranged into these double rooms.
Input
For each data set:
The first line gives two integers, n and m(1<n<=200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs.
Proceed to the end of file.
Output
If these students cannot be divided into two groups, print “No”. Otherwise, print the maximum number of pairs that can be arranged in those rooms.
Sample Input
4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
int n,m,flag;
bool ma[250][250],book[250];
int match[250],color[250];
void dfs(int i,int c) //对点进行染色
{ //二分图如果存在回路，那么这个回路的边数一定是偶数//即从u阵营出发一定回到u阵营，所以如果俩个点的颜色一样//那么他们一定属于同一个阵营for(int j=1; j<=n; j++){if(ma[i][j]) //这俩点存在边，说明属于俩阵营{if(color[j]==0) //如果j没有被染色，则染色{color[j]=-c; //染成和i相反的颜色dfs(j,-c); //进行递归}else if(color[j]==c) //如果颜色相同，然后i和j还有边，{ flag=0; //说明它是奇数回路，不符合二分图定义return ;}}}
}
bool check() //检查是否是二分图
{ flag=1;memset(color,0,sizeof(color));color[1]=1; //将1标记为1；dfs(1,1); return flag; //flag为1说明是二分图，否则不是
}
bool find(int u)
{for(int i=1; i<=n; i++){if(ma[u][i]&&book[i]==0){ //book记录v那边的集合的点book[i]=1; if(match[i]==0||find(match[i]))//如果match符合if那么find将不进行，直接进入if里面{ //否则，进入find，寻找和i匹配的那个点，看看那个点是否能找v里面的其他点，如果递归终点可以找到其他点//那么这一路遍历的点，都将重新赋值，match[i]=u;match[i]=u; //v那边集合匹配到ureturn 1;}}}return 0;
}
int main()
{int p,q;while(cin>>n>>m){int s=0;memset(ma,0,sizeof(ma));memset(match,0,sizeof(match));for(int i=0; i<m; i++){cin>>q>>p;ma[q][p]=ma[p][q]=1;}if(check()==0){printf("No\n");continue; //一定要跳出，，因为它不是二分图}for(int i=1; i<=n; i++){ //这个标记数组一定要在这里情况，因为它是标记的v阵营//是否被走过，所以每一次拿一个u去寻找的时候它都要重新清零memset(book,0,sizeof(book)); if(find(i)) //如果返回值是1，说明就增加了一天边s++;}printf("%d\n",s/2); //因为它要找的是对数，所以除以二} //因为u，v阵营一模一样都是那些人return 0;
}