n<=200000个点m<=500000条边的图，问是否存在一种黑白染色方案使每个点满足：要么它是白色，要么它相邻点是白色；并且，要么它是黑色，要么它相邻点是黑色。
除非某个联通块只有一个点，否则一定有解。并查集维护连通性。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 //#include<assert.h> 6 #include<math.h> 7 //#include<iostream> 8 using namespace std; 9 10 int n,m; 11 #define maxn 200011 12 #define maxm 500011 13 int ufs[maxn],size[maxn]; 14 int find(int x) {return x==ufs[x]?x:(ufs[x]=find(ufs[x]));} 15 void Union(int x,int y) 16 { 17 x=find(x),y=find(y); 18 if (size[x]>size[y]) ufs[y]=x,size[x]+=size[y]; 19 else ufs[x]=y,size[y]+=size[x]; 20 } 21 int x,y; 22 int main() 23 { 24 scanf("%d%d",&n,&m); 25 for (int i=1;i<=n;i++) ufs[i]=i,size[i]=1; 26 for (int i=1;i<=m;i++) 27 { 28 scanf("%d%d",&x,&y); 29 Union(x,y); 30 } 31 bool ans=1; 32 for (int i=1;i<=n;i++) if (ufs[i]==i) if (size[i]==1) ans=0; 33 puts(ans?"TAK":"NIE"); 34 return 0; 35 }