LAOI-6」Yet Another Graph Coloration Problem 题解

晴空一鹤 · 2024-09-07 17:05:37 · 题解

比赛时这题唐了一个小时，写篇题解纪念一下。

首先要求黑白之间至少有 2 条简单路径，这很容易让我们想到缩点相关内容。

考虑使用类似的套路，我们随便选个点开始搜，得到一棵 dfs 搜索树，那么原图就是这棵树加上若干条返祖边（因为是无向图所以没有横叉边）。

记某条返祖边连接的两个节点中深度较深的节点为 x，那么我们可以把 x 的整棵子树染成黑色，子树外染成白色。

那么此时黑白之间显然有 2 条路径：一条是通过 dfs 树的路径，一条是先走 dfs 树到达返祖边的一端，通过返祖边再走 dfs 树的路径。

因此存在返祖边即有解，无解的情况就是树与不连通图。

有解时的方案构造直接模拟上述过程即可。

#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans,vis[200005],u,v,opt,qwq[200005],sum[200005],low[200005],dfn[200005],d;
vector<int>q[200005];
void inline dfs(int x,int fa){
   vis[x]=1;
   for(int i=0;i<q[x].size();i++){
   if(q[x][i]==fa)continue;
   if(vis[q[x][i]]){if(ans==0)ans=1,qwq[x]=1;}
   else {dfs(q[x][i],x);}
   }
}
void inline dfs2(int x,int y){

  vis[x]=1;qwq[x]=max(qwq[x],y);
   for(int i=0;i<q[x].size();i++){
   if(!vis[q[x][i]])
   {dfs2(q[x][i],max(y,qwq[x]));}
   }
}
int main(){
   cin>>t;
   while(t--){
   cin>>n>>m;
   ans=0;
   for(int i=1;i<=n;i++)q[i].clear();
   for(int i=1;i<=n;i++)vis[i]=qwq[i]=0,low[i]=1e9;
   for(int i=1;i<=m;i++){
   cin>>u>>v;
   q[u].push_back(v);
   q[v].push_back(u);
   }d=0;
   dfs(1,0);opt=0;
   for(int i=1;i<=n;i++)
   if(vis[i]==0||ans==0){opt=1;cout<<-1<<"\n";break;}
   if(opt)continue;for(int i=1;i<=n;i++)vis[i]=0;dfs2(1,0);
   for(int i=1;i<=n;i++)
   if(qwq[i])cout<<"B";
   else cout<<"W";
   cout<<"\n";
   }
}