[POI2010]GIL-Guilds（结论题）

题意

给一张无向图，要求你用黑白灰给点染色，且满足对于任意一个黑点，至少有一个白点和他相邻；对于任意一个白点，至少有一个黑点与他相邻，对于任意一个灰点，至少同时有一个黑点和白点和灰点与他相邻，问能否成功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 ;

 }

巴特西

[POI2010]GIL-Guilds（结论题）

题意

题解

最新文章

热门文章