题意：n个点，m条边，每条边连接的两点颜色不同，将所有点染成黑或白，每种颜色至少一个点，求两种颜色分别有几个点，数量大的先输出；
思路：
特判：若人数少于2，则无解；若m=0,则数量分别为n-1,1;
将给定的边双向连接保存，建立无向图；（可能产生多个相互独立的连通图）
枚举每一个连通图的顶点，通过与遍历相邻点遍历一个连通图，遍历过程中染色并记录数量；
sum累加每个连通图中数量最多的点；所求数量即为sum,n-sum;
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; int t,n,m; vector<int>g[500010]; int vis[500010]; int cnt1,cnt2,sum; int dfs(int x) { int i,j,k; for(i=0;i<g[x].size();i++) { k=g[x][i]; if(vis[x]==vis[k]) { return 0; } if(vis[k]==-1) { vis[k]=1-vis[x]; if(vis[k]) cnt2++; else cnt1++; if(!dfs(k)) return 0; } } return 1; } void solve() { int i,j,k; sum=0; memset(vis,-1,sizeof(vis)); if(n<2) { printf("Poor wyh "); return; } if(m==0) { printf("%d %d ",n-1,1); return; } for(i=1;i<=n;i++) { cnt1=0;cnt2=0; if(vis[i]==-1) { vis[i]=0; cnt1++; if(!dfs(i)) { printf("Poor wyh "); return; } sum+=max(cnt1,cnt2); } } printf("%d %d ",sum,n-sum); } int main() { int i,j,k,u,v; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(g,0,sizeof(g));//注意，忘了就wa了 for(i=0;i<m;i++) { scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } solve(); } return 0; }