<题目链接>
题目大意：
有N个人，M组互相认识关系互相认识的两人分别为a,b，将所有人划分为两组，使同一组内任何两人互不认识，之后将两个组中互相认识的人安排在一个房间，如果出现单人的情况则不安排房间。输出最大需要安排房间的数量。
解题分析：
其实题意就是叫我们先判断该图是否为二分图，如果是的话，给出它的最大匹配。判断是否是二分图，我们可以用BFS或DFS对每个节点进行染色，有直接认识关系的人染成不同颜色，判断再染色的过程中是否发生冲突。最后再用匈牙利求出最大匹配。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
;
bool g[N][N],vis[N];
int n,m,ans,linker[N];
bool bfs(){ //用bfs染色法判断该图是否是二分图
queue<int>q;
bool tag[N];
memset(vis,false,sizeof(vis));
q.push(); //先从任意一点开始染色
tag[]=vis[]=true;
while(!q.empty()){
int now=q.front();q.pop();
;i<=n;i++){
if(g[now][i]&&i!=now){
if(vis[i]){
if(tag[now]==tag[i])return false; //如果相连的其它节点已经染色，且染的颜色与当前颜色相同，则说明该图不是二分图
}else{
tag[i]=!tag[now]; //相连的节点染不同的颜色
q.push(i);
vis[i]=true;
}
}
}
}
return true;
}
bool dfs(int x){
;i<=n;i++){
if(g[x][i]&&!vis[i]){
vis[i]=true;
if(!linker[i]||dfs(linker[i])){
linker[i]=x;
return true;
}
}
}
return false;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(g,,sizeof(g));
memset(linker,,sizeof(linker));
while(m--){
int u,v;scanf("%d%d",&u,&v);
g[u][v]=true;
}
if(bfs()){ //该图是二分图
ans=;
;i<=n;i++){ //求出该图的最大匹配
memset(vis,,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d\n",ans);
}else puts("No");
}
;
}
2018-11-11