题意：给出 n 个人，以及 m 对互不认识的关系，剩余的人都互相认识，要将所有人分成两组，组内不能有互不认识的人，要求每组至少有一人，并且第一组人数尽量多，问两组人数或不可能时单独输出

BC 48 场的B题，这两天黑白染色做的不少，要把互不认识的人分在不同的组里，其实就是看整个图是否能够形成二分图，如果不能形成二分图的话，那么说明图中一定存在奇环，那么人就不能分在两个组中而保证组内都认识。所以就是判二分图，用黑白染色，然后将染色后数量多的点分在第一组，剩余分在第二组。但是题中有坑点，首先，人数小于等于1时，本来就分不成两组来保证每组至少一人，所以需要特判，其次如果没有人互不认识，即所有区块都是单点，那么就会出现所有人被分在第一组而第二组没有人的情况，那么就要将一个人分到第二组去。

1 #pragma comment(linker,"/STACK:16777216") 2 #include
      
        3 #include
       
         4  5 typedef long long ll; 6  7 int head[100005],nxt[200005],point[200005],size=0; 8 bool f=0; 9 int num[2];10 int c[100005];11 12 void add(int a,int b){13     point[size]=b;14     nxt[size]=head[a];15     head[a]=size++;16     point[size]=a;17     nxt[size]=head[b];18     head[b]=size++;19 }20 21 void dfs(int a,int x){22     if(f)return;23     c[a]=x;24     num[x]++;25     for(int i=head[a];~i;i=nxt[i]){26         int b=point[i];27         if(c[b]==-1)dfs(b,!x);28         else if(c[b]==x){29             f=1;30             return;31         }32     }33 }34 35 int main(){36     int T;37     scanf("%d",&T);38     while(T--){39         memset(head,-1,sizeof(head));40         size=0;41         f=0;42         memset(c,-1,sizeof(c));43         int n,m;44         scanf("%d%d",&n,&m);45         int i;46         for(i=1;i<=m;i++){47             int a,b;48             scanf("%d%d",&a,&b);49             add(a,b);50         }51         if(n<=1){52             printf("Poor wyh\n");53             continue;54         }55         int ans1=0,ans2=0;56         for(i=1;i<=n&&(!f);i++){57             if(c[i]==-1){58                 num[0]=num[1]=0;59                 dfs(i,1);60                 if(num[0]>num[1]){61                     ans1+=num[0];62                     ans2+=num[1];63                 }64                 else{65                     ans1+=num[1];66                     ans2+=num[0];67                 }68             }69         }70         if(ans2==0){ans1--;ans2++;}71         if(f)printf("Poor wyh\n");72         else printf("%d %d\n",ans1,ans2);73     }74     return 0;75 }