自动搬运

查看原文

来自洛谷，原作者为

	Twilight_star 生而为赢

搬运于2025-08-24 22:02:19，当前版本为作者最后更新于2023-10-04 20:21:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

前置知识

1. 边双连通分量

2. 缩点

题意

给定一张 $n$ 个点 $m$ 条边的无向图，现在想要把这张图定向。

有 $p$ 个限制条件，每个条件形如 $(x_i,y_i)$，表示在新的有向图当中，$x_i$ 要能够沿着一些边走到 $y_i$​​。

现在请你求出，每条边的方向是否能够唯一确定。同时请给出这些能够唯一确定的边的方向。

数据保证有解。

• 若第 $i$ 条边必须得要是 $a_i$​​ 指向 $b_i$ 的，那么这个字符串的第 $i$ 个字符应当为 R；

• 若第 $i$ 条边必须得要是 $b_i$​​ 指向 $a_i$​​ 的，那么这个字符串的第 $i$ 个字符应当为 L；

• 否则，若第 $i$ 条边的方向无法唯一确定，那么这个字符串的第 $i$ 个字符应当为 B。

整体思路

我们能确定一条边的方向，当且仅当至少一组 $x_i$ 到 $y_i$ 必须经过这条边。那实际上也就是这条边是一条“割边”，也就是说删去这条边，左右两端的联通块之间没有任何边相连。

所以我们要去找割边。

但换句话讲，也就是找到一个个边双连通分量，每个边双连通分量内部的边都是不定的，因为这个联通分量内部的点之间互相可以到达且路径不止一条，就算删去了某条边，也依然可以从另一条路径到达。

（不会边双连通分量的同学请左转，P8436 【模板】边双连通分量）

但找到每个边双连通分量后该如何确定中间的“割边”的方向呢？

我们可以暴力去遍历每一个限制条件，但这样会超时。

那我们再想一想会发现，每个边双连通分量内部的边都不确定方向，就不用考虑了（反正输出B就完了）。我们只用考虑剩下的“割边”。

所以我们可以把每个边双连通分量用缩点缩起来，这样点与点之间的边就是原图上的“割边”了。

（不会缩点的同学请右转，P3387 【模板】缩点）

我们知道一棵树的每条边都是“割边”，因为任意删去一条边都会导致这棵树不再联通，所以我们缩完点后的图就可以近似的看成一棵树，只不过它有可能不联通，所以准确来说，是一个森林（很多棵树）。

而树上问题就要比图上问题方便得多了，因为两点之间的路径是唯一的。

不过话说回来，我们要快速确定新图中每条边的方向。 可以想到用树上差分。但可能跟“树上点差分”和“树上边差分”这样的“用来求和的差分”有所不同，我们只用统计每条边的方向。

不妨假设当这个点的差分值为正整数时，这个点通向他父亲的边是向根节点的。

当这个点的差分值为负整数时，这个点通向他父亲的边是向叶子节点的。

而当这个点的差分值为零时，这个点通向他父亲的边就是不定向的。

那我们只用知道这个点的差分值是正还是负。

所以当限制条件为 $x_i$ 和 $y_i$ 时，设数组 $cha$ 为差分数组，我们就将 $cha[x_i]$ 加一，将 $cha[y_i]$ 减一。

差分加减完成后别忘了从根节点开始递归，统计差分值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200005,M=400005;
int n,m,q,head[M],head2[M],cnt2,cnt=1;//用链式前向星存图  
//cnt初始化为1的好处：编号为i^1的边就是编号i的边的反向边 
int dfn[N],low[N],idx;//求边双连通分量的数组 
int col[N],tmp;//每个点属于的边双连通分量的编号，以及边双连通分量的个数 
int cha[N],d[N];//差分数组，新图上节点的深度 
bool b[M];//判断是否为割边 
struct tree//新图 
{
    int v,nxt;
}e[M];
struct node//原图 
{
    int v,nxt,u;
}a[M];
void add(int u,int v)//原图链式前向星存图 
{
    a[++cnt].v=v;
    a[cnt].u=u;//这里存一下边的起点方便后面用 
    a[cnt].nxt=head[u];
    head[u]=cnt;
}
void add2(int u,int v)//新图链式前向星存图 
{
    e[++cnt2].v=v;
    e[cnt2].nxt=head2[u];
    head2[u]=cnt2;
}
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;
}
//这里求边双连通分量的方法是把所有割边“删去”，再搜一遍剩下的图 
void tarjan(int u)//求割边 
{
    dfn[u]=low[u]=++idx;
    for(int i=head[u];i!=0;i=a[i].nxt)
    {
        int v=a[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) b[i]=b[i^1]=1;//标记割边 
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
void dfs1(int u,int num)//当前搜索到第几个点以及当前边双连通分量的编号 
{
    col[u]=num;//编号 
    for(int i=head[u];i!=0;i=a[i].nxt) 
    {
        if(!col[a[i].v]&&b[i]==0) dfs1(a[i].v,num);//如果这条边不是割边就可以访问 
    }
}
void dfs(int u,int fa)//统计差分数组 
{
    d[u]=d[fa]+1;//更新深度 
    for(int i=head2[u];i!=0;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v!=fa) 
        {
            dfs(v,u);
            cha[u]+=cha[v];//统计差分数组 
        }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        add(u,v),add(v,u);//加边 
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);//求割边，（原图不一定联通） 
    for(int i=1;i<=n;i++) if(!col[i]) tmp++,dfs1(i,tmp);//求边双连通分量 
    for(int i=2;i<=cnt;i++)
    {
        if(col[a[i].u]!=col[a[i].v]) add2(col[a[i].u],col[a[i].v]);//缩点+加新边 
    }
    q=read();
    while(q--)
    {
        int u=read(),v=read();
        cha[col[u]]++,cha[col[v]]--;//差分 
    }
    for(int i=1;i<=tmp;i++)if(!d[i])dfs(i,0);//统计差分数组，（新图也不一定联通） 
    for(int i=2;i<=cnt;i+=2)//两个两个地加，过滤掉反向边 
    {
        if(col[a[i].u]==col[a[i].v]) //如果是在同一个边双连通分量里 
        {
            printf("B");//那么边的方向就不确定 
            continue;
        }
        if(d[col[a[i].u]]>d[col[a[i].v]])//如果这条边的起点所在的边双连通分量更深，那么这条边的差分值就在起点 
        {
            if(cha[col[a[i].u]]>0) printf("R");//说明这条边是指向根节点，也就指向这条边的终点
            else if(cha[col[a[i].u]]==0) printf("B");//如果没有一个限制条件经过这条边，就输出B 
            else printf("L");//反之 
        }
        else
        {
            if(cha[col[a[i].v]]>0) printf("L");//说明这条边是指向根节点，也就指向这条边的起点（起点深度更小） 
            else if(cha[col[a[i].v]]==0) printf("B");//同上 
            else printf("R");//反之  （这里不要写成L了） 
        }
    }
    return 0;
}

闲话

（我居然有朝一日能抢到最优解！！！）（2023.10.4）