题解

这种题的解法其实我觉得很多都是随便弄一个生成树，然后再生成树上面加边，然后乱搞。。
这题也是一样，你先随便弄一个生成树
然后你你每次加一条边，如果出现了环，那么这上面所有的边就都是B了
然后我们考虑L和R怎么判，很明显，在判完B之后，剩下的都是无环的
然后又因为数据合法
所以不会出现说方向不同的两条目标路
这启发我们可以使用一个树上差分，然后就知道一条边的指向了
具体看代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100005;
int n,m,p;
struct qq
{int x,y,last,id;
}e[N*2];
int num,last[N];
void init (int x,int y,int z)
{e[++num].x=x;e[num].y=y;e[num].id=z;e[num].last=last[x];last[x]=num;
}
int f2[N],f1[N];//树上差分，这个是要往哪一个方向 
bool vis[N],vis1[N<<1];
char ans[N];
void dfs (int x)
{vis[x]=true;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (vis[y]==false)//这个点访问过了{vis1[e[u].id]=true;dfs(y);}else{if (vis1[e[u].id]==false)//如果这条边没走过，那么就是有环了 {ans[e[u].id]='B';vis1[e[u].id]=true;f1[x]++;f1[y]--;}}}
}
void dfs1 (int x)
{vis[x]=true;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (vis[y]==true) continue;dfs1(y);if (f1[y]>0)//还是一个环ans[e[u].id]='B';else if ((f2[y]>0&&(u&1))||(f2[y]<0&&(!(u&1))))ans[e[u].id]='L';else if ((f2[y]<0&&(u&1))||(f2[y]>0&&(!(u&1))))ans[e[u].id]='R';f1[x]+=f1[y];f2[x]+=f2[y];}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&m);for (int u=1;u<=m;u++){int x,y;scanf("%d%d",&x,&y);init(x,y,u);init(y,x,u);}scanf("%d",&p);for (int u=1;u<=p;u++){int x,y;scanf("%d%d",&x,&y);f2[x]++;f2[y]--;}memset(vis,false,sizeof(vis));memset(vis1,false,sizeof(vis1));for (int u=1;u<=n;u++)if (!vis[u])dfs(u);memset(vis,false,sizeof(vis));for (int u=1;u<=n;u++)if (!vis[u])dfs1(u);for (int u=1;u<=m;u++){if (ans[u]==0) printf("B");else printf("%c",ans[u]);}return 0;
}