题解

思路概述

• 每个限制 $(x_i,y_i)$ 只要求 $x_i$ 能沿着某条有向路径走到 $y_i$，因此在一张无向图中只有桥的方向可能被唯一约束。利用 Tarjan 求桥之后，把整张图按照“删去桥以后得到的双连通分量”缩成点，就得到一棵桥树。
• 在桥树上，任意两个分量之间只有唯一的一条路径。若一个限制的两端在不同分量内，则这条路径上的每条桥都必须被定向，使得流向与限制要求一致。把所有限制在桥树上做差分：对起点分量 +1，终点分量 -1，再沿树自底向上前缀和，得到每条树边上的净流量。
• 对于原图中的每条边：若仍位于同一个分量（不是桥），它的方向永远可以在分量内部调节，因此答案为 B；若是桥，则看它在桥树中的父子关系。若子节点累计流量大于零，则必须从子指向父（输出 R），小于零则反向（输出 L），等于零表示这条桥既可以指向上也可以指向下（输出 B）。

实现细节

• Tarjan 中用 cnt[i] 标记第 i 条有向边是否为桥。随后二次 DFS，在忽略桥的情况下给每个原始点打上分量编号，并收集分量之间的桥，建立桥树。
• 差分流程利用树上前缀和：遍历所有限制，先把端点映射到对应分量，再在桥树上对两个分量分别 +1/-1；之后在桥树上做一次 DFS 汇总子树贡献即可得到每个分量到父亲边的净流量。

正确性说明

• 非桥边所在的双连通分量内部存在环，可以通过调节环上的方向消解任意单条边的方向要求，因此其方向不会被唯一限定。
• 桥树是一棵树，同一路径上所有桥的方向必须一致才能让限制成立。对路径做差分并取前缀和等价于统计有多少限制必须沿该树边从子向父流通（正数）或从父向子流通（负数），从而得到唯一确定的方向。
• 若某条桥上的净流量为零，表示对它的两个方向都没有强制要求，因此它的方向不唯一。

复杂度

Tarjan、建树和两次 DFS 均为线性复杂度，总时间复杂度为 $O(n+m)$，额外空间也为 $O(n+m)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,p,head[N],pre[N*2],to[N*2],nex[N*2],e,dfn[N],idx,sum;
int deep[N],dif[N];
bool cnt[N*2];
vector<int> d[N];
inline int read()//快读 
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void add(int a,int b){
	pre[e]=a;
	to[e]=b;
	nex[e]=head[a];
	head[a]=e;
	e++;
}
inline void Tarjan(int x,int fa){
	//cout<<"?"<<x<<endl;
	dif[x]=dfn[x]=++idx;
	for(register int i=head[x];i!=-1;i=nex[i]){
		if(dfn[to[i]]==0){
			Tarjan(to[i],x);
			dif[x]=min(dif[x],dif[to[i]]);
			if(dif[to[i]]>dfn[x]) cnt[i]=cnt[i^1]=1;
		}
		else if(to[i]!=fa) dif[x]=min(dif[x],dfn[to[i]]);
	}
}
inline void dfs(int x){
	dfn[x]=sum;
	for(register int i=head[x];i!=-1;i=nex[i]){
		if(cnt[i]==0 and dfn[to[i]]==0) dfs(to[i]);
	}
}
void ddfs(int x,int fa){
	//cout<<"???????"<<x<<" "<<fa<<endl;
	deep[x]=deep[fa]+1;
	for(register int i=0;i<d[x].size();i++){
		if(d[x][i]==fa) continue;
		ddfs(d[x][i],x);
		dif[x]+=dif[d[x][i]];
	}
}
int main(){
//	freopen("oneway9.in","r",stdin);
//	freopen("oneway.out","w",stdout);
	n=read();m=read();
	for(register int i=1;i<=n;i++) head[i]=-1;
	int u,v;
	for(register int i=1;i<=m;i++){
		u=read();v=read();
		add(u,v);
		add(v,u);
	}
	for(register int i=1;i<=n;i++){
		if(dfn[i]) continue;
		Tarjan(i,0);
	}
	for(register int i=1;i<=n;i++) dfn[i]=0;
	for(register int i=1;i<=n;i++){
		if(dfn[i]) continue;
		sum++;
		dfs(i);
	}
	for(register int i=0;i<e;i++){
		if(dfn[pre[i]]==dfn[to[i]]) continue;
		//cout<<"??"<<dfn[pre[i]]<<" "<<dfn[to[i]]<<endl;
		d[dfn[pre[i]]].push_back(dfn[to[i]]);
	}
	for(int i=1;i<=sum;i++) dif[i]=0;
	p=read();
	while(p--){
		u=read();v=read();
		u=dfn[u];v=dfn[v];
		dif[u]++;
		dif[v]--;
	}
	for(register int i=1;i<=sum;i++){
		if(deep[i]!=0) continue;
		ddfs(i,0);
	}
	for(register int i=0;i<e;i+=2){
		int a=dfn[pre[i]],b=dfn[to[i]];
		if(a==b) printf("B");
		else if(deep[a]>deep[b]){
			if(dif[a]>0) printf("R");
			else if(dif[a]<0) printf("L");
			else printf("B");
		}
		else{
			if(dif[b]>0) printf("L");
			else if(dif[b]<0) printf("R");
			else printf("B");
		}
	}
	return 0;
}