自动搬运

查看原文

来自洛谷，原作者为

	Wight_sl 把目光放的极其的长远,你就会发现其实天也在你的脚下

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