wyh2000 and pupil
青年理论计算机科学家wyh2000在教导他的小学生。共同拥有n个小学生，编号为1−n。为了添加小学生之间的凝聚力，wyh2000决定将全部小学生分成2组，每组都至少有1个人。可是有些小学生之间并不认识，并且假设a不认识b，那么b也不认识a。
Wyh2000希望每组中的小学生都互相认识。并且第一组的人要尽可能多。 请你帮wyh2000求出第一组和第二组的人数是多少。假设找不到分组方案，则输出"Poor wyh"。
第一行一个数T，表示数据组数。对于每组数据，第一行两个数n,m，表示小学生数量和互相不认识的小学生的数量。
接下来m行，每行两个数x,y(x<y)，表示x不认识y，y不认识x。
保证一对(x,y)仅仅会出现一次。
T≤10,0≤n,m≤100000
对于每组数据，输出答案。
28 53 45 61 25 83 55 42 34 53 42 4
5 3Poor wyh
/*Author: 2486Memory: 7448 KB Time: 592 MSLanguage: G++ Result: AcceptedVJ RunId: 4055769 Real RunId: 14058285Public: No Yes*//*假设a不认识b，那么在a,b间连一条边，这样有解当且仅当这张图是二分图。由于可能有多个二分图。而题目要求第一组的人尽可能多，所以贪心的选择就可以。
要注意m=0的情况。
*/ #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn=100000+5; vector<int>G[maxn]; int col[maxn],T; int n,m,a,b,acnt,bcnt; void init(int x) { for(int i=1; i<=x; i++) { G[i].clear(); } } bool bfs(int u) { queue<int>k; k.push(u); col[u]=1; while(!k.empty()) { int s=k.front(); if(col[s]==1)acnt++; else bcnt++; k.pop(); for(int i=0; i<G[s].size(); i++) { if(col[G[s][i]]==-1) { col[G[s][i]]=!col[s]; k.push(G[s][i]); continue; } if(col[G[s][i]]==col[s])return false; } } return true; } void slove() { memset(col,-1,sizeof(col)); bool flag=false; int Max=0; for(int i=1; i<=n; i++) { acnt=0,bcnt=0; if(col[i]==-1&&!bfs(i)) { flag=true; break; } Max+=max(acnt,bcnt);//必须这么做，由于这里面为1的或者为0的不一定就是同一阵营。
} if(flag)printf("Poor wyh\n"); else printf("%d %d\n",Max,n-Max); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); init(n); for(int i=0; i<m; i++) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } if(n<2) {//题目要求 printf("Poor wyh\n"); continue; } if(m==0) {//题目要求 printf("%d 1\n",n-1); continue; } slove(); } return 0; }