题意:n个点,m条边,每条边连接的两点颜色不同,将所有点染成黑或白,每种颜色至少一个点,求两种颜色分别有几个点,数量大的先输出;
思路:
特判:若人数少于2,则无解;若m=0,则数量分别为n-1,1;
将给定的边双向连接保存,建立无向图;(可能产生多个相互独立的连通图)
枚举每一个连通图的顶点,通过与遍历相邻点遍历一个连通图,遍历过程中染色并记录数量;
sum累加每个连通图中数量最多的点;所求数量即为sum,n-sum;
#include#include #include #include #include using namespace std;int t,n,m;vector g[500010];int vis[500010];int cnt1,cnt2,sum;int dfs(int x){ int i,j,k; for(i=0;i