时间限制：0.25s
空间限制：4M
题意：
将n（n<200）个点分成两个集合，给出m(m<=30000)对不能在一个集合的点对，判断能否分成满足要求的集合，输出其中一个集合和集合的总数目。
Solution：
二分图染色，dfs即可。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n,m,x,y,tol;
bool g[209][209];
int f[30009];
int dfs(int x){
for(int i=1;i<=n;i++){
if(!g[x][i]) continue;
if(f[i]==-1){
f[i]=!f[x];
if(f[i]==0) tol++;
if(dfs(i)) return 1;
}
else
if(f[i]==f[x])
return 1;
}
return 0;
}
int main(){
scanf("%d %d",&n,&m);
memset(g,0,sizeof g);
memset(f,-1,sizeof f);
for(int i=1;i<=m;i++){
scanf("%d %d",&x,&y);
g[x][y]=g[y][x]=1;
}
for(int i=1;i<=n;i++){
if(f[i]!=-1) continue;
f[i]=0,tol++;
if(dfs(i)){
puts("no");
return 0;
}
}
printf("yes\n%d\n",tol);
for(int i=1;i<=n;i++)
if(f[i]==0) printf("%d ",i);
return 0;
}
原文：http://www.cnblogs.com/keam37/p/3915112.html