题意
给一张无向图，要求你用黑白灰给点染色，且满足对于任意一个黑点，至少有一个白点和他相邻；对于任意一个白点，至少有一个黑点与他相邻，对于任意一个灰点，至少同时有一个黑点和白点和灰点与他相邻，问能否成功n(<=200000) and m(<=500000)
题解
我一开始以为是一定成功。
结果忘了一个独立点的情况。
我们知道树一定是二分图。
所以用并查集求出每个联通块的随便一个生成树，跑bfs黑白染色即可。（甚至用不到灰色）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int N=;
const int M=;
int fa[N],n,m,cnt,book[N],col[N],head[N];
struct edge{
int to,nxt;
}e[M*];
void add(int u,int v){
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void bfs(int s,int c){
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(col[v]==-){
col[v]=col[u]^;
q.push(v);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
int x=find(u);
int y=find(v);
if(x==y)continue;
book[u]=book[v]=;
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++){
if(book[i]==){
printf("NIE");
return ;
}
}
printf("TAK\n");
memset(col,-,sizeof(col));
for(int i=;i<=n;i++){
if(col[i]==-){
col[i]=;
bfs(i,);
}
}
for(int i=;i<=n;i++){
if(col[i]==)printf("K\n");
else printf("S\n");
}
return ;
}