题意：有n个学生，有m对人是认识的，每一对认识的人能分到一间房，问能否把n个学生分成两部分，每部分内的学生互不认识，而两部分之间的学生认识。如果可以分成两部分，就算出房间最多需要多少间，否则就输出No。
首先判断是否为二分图，然后判断最大匹配
Sample Input
4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6
Sample Output
No
3
#include<iostream>
#include<string.h>
#include<vector>
#include<cstdio>
using namespace std;
#define MAXN 202
vector<int>EV[MAXN];
int linker[MAXN];
bool used[MAXN];
int uN;
int matchs[MAXN],cnt[MAXN];
bool dfs(int u)
{
int i;
for(i=;i<EV[u].size();i++)
{
int v=EV[u][i];
if(!used[v])
{
used[v]=true;
if(linker[v]==-||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int res=;
int u;
memset(linker,-,sizeof(linker));
for(u=;u<=uN;u++)
{
memset(used,false,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
bool judge(int x,int y) //交叉染色法判断二分图
{
int i;
for(i=;i<EV[x].size();i++)
{
if(cnt[EV[x][i]]==)
{
cnt[EV[x][i]]=-*y;
matchs[EV[x][i]]=true;
if(!judge(EV[x][i],-*y)) return false;
}
else if(cnt[EV[x][i]]==y) return false;
}
return true;
}
bool matched()
{
int i;
memset(matchs,false,sizeof(matchs));
for(i=;i<=uN;i++)
{
if(EV[i].size()&&!matchs[i])
{
memset(cnt,,sizeof(cnt));
cnt[i]=-;
matchs[i]=true;
if(!judge(i,-)) return false;
}
}
return true;
}
int main()
{
int m;
int i;
int u,v;
while(scanf("%d%d",&uN,&m)!=EOF)
{
for(i=;i<=uN;i++)
if(EV[i].size()) EV[i].clear();
while(m--)
{
scanf("%d%d",&u,&v);
EV[u].push_back(v);
EV[v].push_back(u);
} if(matched())
printf("%d\n",hungary()/);
else printf("No\n");
}
return ;
}