第一次用vector解得题，值得纪念，这道题是二染色问题，我用bfs解得，就是染色，判断，计数问题，其
实挺简单的，就是得判一下特殊情况，当n<2的时候就不能有解，因为题目要求每个组至少有一个人，当没有不认识的
人的时候就是一个组是n-1，另一个组人数为1
上代码：
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>#include<vector>#include<queue> using namespace std;int visit[100005];int n,m,flag,ans1,ans2;vector<int>v[100005];int bfs(int x){queue<int>q;q.push(x);visit[x] = 1;while(!q.empty()){int y = q.front();q.pop();if(visit[y] == 1)ans1++;elseans2++;for(int i=0; i<v[y].size(); i++){if(visit[v[y][i]]==-1){visit[v[y][i]] = !visit[y];q.push(v[y][i]);}else{if(visit[v[y][i]]==visit[y]){return 0;}}}}return 1;}void solve(){int Max = 0;memset(visit,-1,sizeof(visit));for(int i=1; i<=n; i++){ans1 = ans2 =0;//printf("size = %d i = %d\n",v[i].size(),i);if(v[i].size()==0)continue;if(visit[i]==-1&&!bfs(i)){flag = 1;break;}Max += min(ans1,ans2);//printf("ans1 = %d ans2 = %d\n",ans1,ans2);}if(flag)printf("Poor wyh\n");elseprintf("%d %d\n",n – Max,Max);return ;}int main(){int T,c,i,j,a,b;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);for(i=1; i<=n; i++)v[i].clear();for(i=1; i<=m; i++){scanf("%d%d",&a,&b);v[a].push_back(b);v[b].push_back(a);}if(n < 2){puts("Poor wyh");continue;}if(m == 0){printf("%d 1\n",n-1);continue;} flag = 0;solve();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，片的时光如浮云般流过，我们的青春单薄的穿梭在蓝天之上。
