题意：n个学生，m对关系，每一对互相认识的能住一个房间。问否把这些学生分成两组，要求每组的学生都互不认识。求最多须要多少个房间。
能否分成两组？也就是说推断是不是二分图，推断二分图的办法，用染色法
把初始点染成黑色，然后与之相连的染成白色，反复，使路径黑白相间，
假设当前点的颜色和与他相连点的颜色同样时，则说明这个图不是二分图
求最多须要多少个房间？也就是求最大匹配数。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <math.h>
#define init(a) memset(a,0,sizeof(a))
#define PI acos(-1,0)
using namespace std;
const int maxn = 310;
const int maxm = 100001;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b
const int N = 50010;
int ma[maxn][maxn];
int line[maxn],color[maxn];
bool vis[maxn];
int k,n,m;
bool flag;
int DFS(int u)
{
for(int v = 1;v<=n;v++)
{
if(ma[u][v]==1 && !vis[v])
{
vis[v] = 1;
if(line[v]==-1 || DFS(line[v]))
{
line[v] = u;
return 1;
}
}
}
return 0;
}
void dfs(int u,int st)
{
if(flag == false)
return ;
for(int v = 1;v <= n;v++)
{
if(ma[u][v])
{
if(!color[v])
{
color[v]= -st;//黑染白 / 白染黑
dfs(v,color[v]);
}
else if(color[v]==st)
{
flag = false;
return;
} }
} }
bool judge()
{
flag = true;
color[1] = 1 ;//1代表黑色，-1代表白色
dfs(1,1) ;
return flag;
}
int K_M()
{
int ans = 0;
memset(line,-1,sizeof(line));
for(int i = 1;i<=n;i++)
{
init(vis);
ans += DFS(i);
}
return ans;
}
int main()
{
int a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(ma);
memset(color,0,sizeof(color));
for(int i = 1;i<=m;i++)
{
scanf("%d%d",&a,&b);
ma[a][b] = 1;
}
if(!judge())
{
puts("No");
continue;
}
int ans = K_M();
printf("%d\n",ans);
}
return 0;
}