P10298 [CCC 2024 S4] Painting Roads 题解

Wight_sl · 2024-04-04 00:01:42 · 题解

思路

在图上比较难考虑路径，考虑将图转换为树，选 n-1 条边染色，对于一条灰色的边 u,v，它对生成树上边颜色的限制为 u 到 \operatorname{lca}(u,v) 的路径颜色交替出现，v 到 \operatorname{lca}(u,v) 的路径颜色交替出现，且 \operatorname{lca}(u,v) 到 u,v 子树的第一条边颜色不同，前两个限制是比较好满足的，按边的深度奇偶性给边染色即可。考虑解决最后一个限制，容易发现如果这条灰色边在生成树中是返祖边时，这条限制一定满足，横叉边时则不一定满足。注意到这张图是无向图，无向图的 dfs 生成树的非树边全是返祖边。那么只直接在 dfs 生成树上将边按奇偶染色即可，时间复杂度为 O(n+m)。实现注意图不一定连通，可能是 dfs 森林。

代码

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,m,col[N];//col用来记录深度奇偶性，-1表示灰色的边 
vector<pair<int,int> > a[N];//用pair存图 点 边的编号 
bool v[N];//标记数组
//dfs生成树 
void dfs(int u,int y){
    v[u]=1;//标记 
    for(int i=0;i<a[u].size();i++){//auto迭代器的等价 
        int x=a[u][i].first,z=a[u][i].second;
        if(v[x]) continue;//如果点以及遍历过了那么直接跳过 
        col[z]=y&1;//否则便通过奇偶性存下 
        dfs(x,y+1);
    }
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        a[u].push_back({v,i});
        a[v].push_back({u,i});
        col[i]=-1;//初始化全是灰色 
    }
    for(int i=1;i<=n;i++){
        if(!v[i]){
            dfs(i,0);//没走过的点就搜一下 
        }
    }
    for(int i=1;i<=m;i++){
        if(col[i]==-1) putchar('G');
        if(col[i]==0)  putchar('R');//偶数为红 
        if(col[i]==1)  putchar('B');//奇数为蓝 
    }
    return 0;
}