题目描述
给定一张 (n) 个点 (m) 条边的无向图，现在想要把这张图定向。
有 (p) 个限制条件，每个条件形如 ((xi,yi)) ，表示在新的有向图当中，(x_i) 要能够沿着一些边走到 (y_i) 。
现在请你求出，每条边的方向是否能够唯一确定。同时请给出这些能够唯一确定的边的方向。
输入格式
第一行两个空格隔开的正整数 (n,m) 。
接下来 (m) 行，每行两个空格隔开的正整数 (a_i,b_i) ，表示 (a_i,b_i) 之间有一条边。
接下来一行一个整数 (p)，表示限制条件的个数。
接下来 (p) 行，每行两个空格隔开的正整数 (x_i,y_i)，描述一个 ((x_i,y_i)) 的限制条件。
输出格式
输出一行一个长度为 (m) 的字符串，表示每条边的答案：
-
若第 (i) 条边必须得要是 (a_i) 指向 (b_i) 的，那么这个字符串的第 (i) 个字符应当为
R； -
若第 (i) 条边必须得要是 (b_i) 指向 (a_i) 的，那么这个字符串的第 (i) 个字符应当为
L； -
否则，若第 (i) 条边的方向无法唯一确定，那么这个字符串的第 (i) 个字符应当为
B。
样例
样例输入
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
样例输出
BBRBBL
数据范围与提示
对于所有测试点，有 (1le n,m,ple 100 000;1le a_i,b_i,x_i,y_ile n) 。
-
子任务 1（(30\%)）：有 (n,mle 1000;ple 100) ；
-
子任务 2（(30\%)）：有 (ple 100) ；
-
子任务 3（(40\%)）：无特殊限制。
题解
在同一个点双内的显然不能完全确定
所以先Tarjan找点双并缩点
对于剩下的点与询问，就是在一棵树上了，随便搞一搞就好了
我是用的一种奇怪的方法
对于一个点，它的权值记录了它和它的父亲之间的边的方向
对于一个询问，找到询问中两个点的LCA，然后在两个点都打上LCA的标记，代表它们到LCA的这段路径上的所有边的方向全部为某个方向
由于题目保证无冲突，所以是不会有一条边会被赋值两次的
所有标记打完后，一遍dfs处理完所有标记就好了
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=100000+10,inf=0x3f3f3f3f;
int n,m,q,e=1,beg[MAXN],nex[MAXN<<1],to[MAXN<<1],DFN[MAXN],LOW[MAXN],Visit_Num,bridge[MAXN<<1],cnt,bel[MAXN],qto[MAXN<<1],qnex[MAXN<<1],qbeg[MAXN],Jie[MAXN][21],up[MAXN],dep[MAXN],qe,mk[MAXN],ps[MAXN],nt;
struct node{
int u,v;
};
node side[MAXN];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!=' ')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
inline void qinsert(int x,int y)
{
qto[++qe]=y;
qnex[qe]=qbeg[x];
qbeg[x]=qe;
}
inline void Tarjan(int x,int f)
{
DFN[x]=LOW[x]=++Visit_Num;ps[x]=nt;
for(register int i=beg[x];i;i=nex[i])
if(!DFN[to[i]])
{
Tarjan(to[i],x);
chkmin(LOW[x],LOW[to[i]]);
if(LOW[to[i]]>DFN[x])bridge[i]=bridge[i^1]=1;
}
else if(DFN[to[i]]<DFN[x]&&to[i]!=f)chkmin(LOW[x],DFN[to[i]]);
}
inline void dfs(int x)
{
DFN[x]=1;bel[x]=cnt;
for(register int i=beg[x];i;i=nex[i])
if(bridge[i])continue;
else if(!DFN[to[i]])dfs(to[i]);
}
inline void idfs(int x,int f)
{
Jie[x][0]=f;dep[x]=dep[f]+1;
for(register int i=qbeg[x];i;i=qnex[i])
if(qto[i]==f)continue;
else idfs(qto[i],x);
}
inline void init()
{
for(register int j=1;j<=19;++j)
for(register int i=1;i<=cnt;++i)Jie[i][j]=Jie[Jie[i][j-1]][j-1];
}
inline int LCA(int u,int v)
{
if(dep[u]<dep[v])std::swap(u,v);
if(dep[u]>dep[v])
for(register int i=19;i>=0;--i)
if(dep[Jie[u][i]]>=dep[v])u=Jie[u][i];
if(u==v)return u;
for(register int i=19;i>=0;--i)
if(Jie[u][i]!=Jie[v][i])u=Jie[u][i],v=Jie[v][i];
return Jie[u][0];
}
inline void edfs(int x,int f)
{
for(register int i=qbeg[x];i;i=qnex[i])
if(qto[i]!=f)edfs(qto[i],x),chkmin(up[x],up[qto[i]]);
if(up[x]<dep[f])mk[f]=mk[x];
}
int main()
{
read(n);read(m);
for(register int i=1;i<=m;++i)
{
int u,v;read(u);read(v);
insert(u,v);insert(v,u);
side[i]=(node){u,v};
}
for(register int i=1;i<=n;++i)
if(!DFN[i])++nt,Tarjan(i,0);
memset(DFN,0,sizeof(DFN));
for(register int i=1;i<=n;++i)
if(!DFN[i])++cnt,dfs(i);
for(register int i=1,u,v;i<=m;++i)
if((u=bel[side[i].u])!=(v=bel[side[i].v]))qinsert(u,v),qinsert(v,u);
for(register int i=1;i<=cnt;++i)
if(!dep[i])idfs(i,0);
init();
memset(up,inf,sizeof(up));
read(q);
while(q--)
{
int x,y,lca;read(x);read(y);
if(bel[x]==bel[y]||ps[x]!=ps[y])continue;
x=bel[x],y=bel[y];lca=LCA(x,y);
if(x!=lca)chkmin(up[x],dep[lca]),mk[x]=-1;
if(y!=lca)chkmin(up[y],dep[lca]),mk[y]=1;
}
edfs(1,0);
for(register int i=1,u,v;i<=m;++i)
{
u=side[i].u,v=side[i].v;
if(bel[u]==bel[v])putchar('B');
else
{
u=bel[u],v=bel[v];
if(dep[u]>dep[v])
{
if(mk[u]==-1)putchar('R');
else if(mk[u]==1)putchar('L');
else putchar('B');
}
else
{
if(mk[v]==-1)putchar('L');
else if(mk[v]==1)putchar('R');
else putchar('B');
}
}
}
puts("");
return 0;
}