@loj - 2480@ 「CEOI2017」One-Way Streets

目录


@description@

给定一张 n 个点 m 条边的无向图,现在想要把这张图定向。
有 p 个限制条件,每个条件形如 \((x_i, y_i)\),表示在新的有向图当中,\(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

数据范围与提示
对于 100% 的数据,有 1 <= n, m, p <= 100000。

@solution@

对于无向图转有向图的连通性问题有一个比较常见的结论可以使用:
一个无向图中的边双连通分量可以转成有向图中的强连通分量。
至于为什么,可以结合 tarjan 算法理解:将树边向下连,返祖边向上连,就可以将一个边双连通分量转成强连通分量。

对于一个强连通分量,它内部的点可以互相到达。
同时,将强连通分量内部所有边反转,依然可以互达。这意味着强连通分量内的边总是不可确定方向的。
对应到原图中,原图中边双连通分量内部的边不可以确定方向。

考虑一个限制 (xi, yi),如果同属一个双连通分量则显然可以转成强连通满足限制。
如果不属于同一个双连通分量,因为边双缩点后得到了一棵树,那么 xi -> yi 这条路径上所有缩点后的树边就可以确定方向了。

具体实现,因为总是有解,所以我们可以给每条边设置一个初始为 0 的边权。将 < 0 记为向上,= 0 记为不确定,> 0 记为向下。
然后根据每个限制,对边权加加减减,做一遍树上差分即可。

@accepted code@

#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(G, x) for(graph::edge *p = G.adj[x];p;p = p->nxt)
const int MAXN = 100000;
struct graph{
    struct edge{
        int to;
        edge *nxt, *rev;
    }edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt;
    graph() {ecnt = edges;}
    void addedge(int u, int v) {
        edge *p = (++ecnt), *q = (++ecnt);
        p->to = v, p->nxt = adj[u], adj[u] = p;
        q->to = u, q->nxt = adj[v], adj[v] = q;
        p->rev = q, q->rev = p;
    }
}G1, G2;
int dfn[MAXN + 5], low[MAXN + 5], dcnt = 0;
int stk[MAXN + 5], id[MAXN + 5], tp = 0, tot = 0;
void dfs1(int x, graph::edge *pre) {
    stk[++tp] = x;
    dfn[x] = low[x] = (++dcnt);
    rep(G1, x) {
        if( p->rev == pre ) continue;
        if( dfn[p->to] ) low[x] = min(low[x], dfn[p->to]);
        else dfs1(p->to, p), low[x] = min(low[x], low[p->to]);
    }
    if( low[x] >= dfn[x] ) {
        tot++;
        do{
            id[stk[tp]] = tot;
        }while( stk[tp--] != x );
    }
}
int fa[MAXN + 5];
void dfs2(int x, int f) {
    fa[x] = f;
    rep(G2, x) {
        if( p->to != f )
            dfs2(p->to, x);
    }
}
bool tag[MAXN + 5]; int d[MAXN + 5];
void dfs3(int x) {
    tag[x] = true;
    rep(G2, x) {
        if( !tag[p->to] )
            dfs3(p->to), d[x] += d[p->to];
    }
}
int a[MAXN + 5], b[MAXN + 5], n, m, p;
int main() {
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++) {
        scanf("%d%d", &a[i], &b[i]);
        G1.addedge(a[i], b[i]);
    }
    for(int i=1;i<=n;i++)
        if( !dfn[i] ) dfs1(i, NULL);
    for(int i=1;i<=m;i++)
        if( id[a[i]] != id[b[i]] )
            G2.addedge(id[a[i]], id[b[i]]);
    for(int i=1;i<=tot;i++)
        if( !fa[i] ) dfs2(i, 0);
    scanf("%d", &p);
    for(int i=1;i<=p;i++) {
        int x, y; scanf("%d%d", &x, &y);
        d[id[x]]--, d[id[y]]++;
    }
    for(int i=1;i<=tot;i++)
        if( !tag[i] ) dfs3(i);
    for(int i=1;i<=m;i++)
        if( id[a[i]] == id[b[i]] ) putchar('B');
        else {
            if( fa[id[a[i]]] == id[b[i]] ) {
                if( d[id[a[i]]] < 0 ) putchar('R');
                else if( d[id[a[i]]] == 0 ) putchar('B');
                else putchar('L');
            }
            else {
                if( d[id[b[i]]] > 0 ) putchar('R');
                else if( d[id[b[i]]] == 0 ) putchar('B');
                else putchar('L');
            }
        }
    puts("");
}

@details@

其实不止树上差分,还有很多方法可以实现最后给边定向,比如并查集。

而且说实话,并查集还要自然一点。

上一篇:360浏览器以兼容模式运行


下一篇:DAY6《Linux就该这么学》