自动搬运

查看原文

来自洛谷，原作者为

	晴空一鹤 恰似人间惊鸿客，墨染星辰云水间

搬运于2025-08-24 23:03:34，当前版本为作者最后更新于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";
   }
}