P11022 「LAOI-6」Yet Another Graph Coloration Problem 用 Tarjan 求点双连通分量，找一个大小 ≥3 的分量，将其节点一半染 B、一半染 W，然后从这个分量开始 BFS 往外染色，同色向外扩展，保证不同色节点在同一个点双内，从而满足题目要求的“任意异色节点间至少有两条不相交路径”。若图不连通或所有点双大小 代码： #include using namespace std; const int N=2e5+5; vector> g[N]; int dfn[N],low[N],bel[N],sz[N],idx,cnt; stack st; char col[N]; vector comp[N]; void tj(int u,int fa){ dfn[u]=low[u]=++idx; st.push(u); for(auto [v,id]:g[u]){ if(!dfn[v]){ tj(v,u); low[u]=min(low[u],low[v]); } else if(v!=fa){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ ++cnt; while(1){ int x=st.top();st.pop(); bel[x]=cnt; comp[cnt].push_back(x); if(x==u)break; } } } void bfs(int u,char c){ queue q; q.push(u); while(!q.empty()){ int x=q.front();q.pop(); if(col[x]) continue; col[x]=c; for(auto [v,id]:g[x]){ if(!col[v]) q.push(v); } } } void solve(){ int n,m; cin>>n>>m; idx=cnt=0; for(int i=1;i>u>>v; g[u].push_back({v,i}); g[v].push_back({u,i}); } tj(1,0); for(int i=1;i=3){ bg=i; break; } } if(bg==-1){ cout>T; while(T--){ solve(); } return 0; } `#include using namespace std; const int N=2e5+5; vectorint,int>> g[N]; int dfn[N],low[N],bel[N],sz[N],idx,cnt; stackint> st; char col[N]; vectorint> comp[N]; void tj(int u,int fa){ dfn[u]=low[u]=++idx; st.push(u); for(auto [v,id]:g[u]){ if(!dfn[v]){ tj(v,u); low[u]=min(low[u],low[v]); } else if(v!=fa){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ ++cnt; while(1){ int x=st.top();st.pop(); bel[x]=cnt; comp[cnt].push_back(x); if(x==u)break; } } } void bfs(int u,char c){ queueint> q; q.push(u); while(!q.empty()){ int x=q.front();q.pop(); if(col[x]) continue; col[x]=c; for(auto [v,id]:g[x]){ if(!col[v]) q.push(v); } } } void solve(){ int n,m; cin>>n>>m; idx=cnt=0; for(int i=1;i g[i].clear(); comp[i].clear(); dfn[i]=low[i]=bel[i]=0; col[i]=0; } while(!st.empty())st.pop(); for(int i=1;i int u,v; cin>>u>>v; g[u].push_back({v,i}); g[v].push_back({u,i}); } tj(1,0); for(int i=1;i if(!dfn[i]){ cout"-1\n"; return; } } int bg=-1; for(int i=1;i if(comp[i].size()>=3){ bg=i; break; } } if(bg==-1){ cout"-1\n"; return; } int hf=comp[bg].size()/2; for(int i=0;icomp[bg].size();i++){ int u=comp[bg][i]; col[u]=(i'B':'W'); } for(int u:comp[bg]){ for(auto [v,id]:g[u]){ if(!col[v]){ bfs(v,col[u]); } } } for(int i=1;i if(!col[i]) col[i]='B'; coutcol[i]; } cout"\n"; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int T; cin>>T; while(T--){ solve(); } return 0; }`
P11022 「LAOI-6」Yet Another Graph Coloration Problem
笔记