题意：
有n个学生，有m对人是认识的，每一对认识的人能分到一间房，问能否把n个学生分成两部分，每部分内的学生互不认识，而两部分之间的学生认识。如果可以分成两部分，就算出房间最多需要多少间，否则就输出No。
思路：
判断是否是二分图，并输出最大匹配数。用'临点填色法'判断，相邻点异色，发现同色则不成立，然后匈牙利算法， 求出个数除2。注：匈牙利算法时间复杂度 '邻接表': O(mn)，邻接矩阵: O(n^3)。
代码：
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std; bool map[][];//连接图
bool visit[];//判断是否访问过
int link[];// 当前链接表
int judge[];// 判断二分图时 0-1表
int queue[];
int n,m; bool BFS()
{ //二分图BFS判断
int v,start = ,end = ;
queue[] = ;
for(int i=;i<=n;i++)
judge[i] = -;
v = queue[start];
judge[] = ;
memset(visit,,sizeof(visit));
while(start<end)
{
v= queue[start];
for(int i = ;i <= n; i++)
{
if(map[v][i])
{
if(judge[i] == -)
{
judge[i] = (judge[v]+)%;
queue[end++] = i;
}
else
{
if(judge[i] == judge[v])
return false;
}
}
}
start++;
}
return true;
} int maxmatch(int r)
{
for(int i=;i<=n;i++)
{
if(map[r][i] && visit[i] == )
{
visit[i] = ;
if(link[i]== || maxmatch(link[i]))
{
link[i] = r;
return ;
}
}
}
return ;
} int main()
{
while(cin>>n>>m)
{
memset(map,,sizeof(map));
int a,b;
for(int i=;i<m;i++)
{
cin>>a>>b;
map[a][b] = ;
map[b][a] = ;
}
//judge the bipartite graph
if(!BFS()) {
cout<<"No"<<endl;
continue;
}
//the maximum number of pair
int num = ;
memset(link,,sizeof(link));
for(int i=;i<=n;i++)
{
memset(visit,,sizeof(visit));
if(maxmatch(i)) num++;
}
cout<< num/ <<endl;
}
return ;
}