Visits: 334

ARC092F Two Faced Edges

题意

• 给定一张 $n$ 个点 $m$ 条边无重边无自环的有向图。
• 求每条边反向后整张图的强连通分量个数有没有变化。
• $n \le 10^3$，$m \le 2 \times 10^5$。

题解

直接上结论：

对于一条边 $u \to v$，反向后整张图的强连通分量个数有变化当且仅当恰好满足下列两个条件中的一个：

1. 忽略这条边后，$u$ 能到达 $v$。
2. 忽略这条边后，$v$ 能到达 $u$。

后者是否忽略没区别，直接对于每个点 dfs 出能到达的点即可，时间复杂度 $\mathcal O(nm)$。

对于前者，我们实际上要求的就是从 $u$ 开始第一条边不走 $u \to v$ 的情况下能否到达 $v$。

考虑对于所有 $u$ 相同的边一起计算，设出边分别为 $v_{1\dots k}$。

首先按照 $v_{1\dots k}$ 的顺序 dfs 一遍，记录下每个点 $k$ 是从哪个 $v_i$ 到达的，记作 $p(k)$。

然后按照 $v_{k \dots 1}$ 的顺序 dfs 一遍，同样记录下每个点 $k$ 是从哪个 $v_i$ 到达的，记作 $q(k)$。

对于一个 $v_i$，若 $p(v_i) = q(v_i) = v_i$，则说明从 $u$ 开始第一条边不走 $u \to v$ 的情况下无法到达 $v$，否则说明可以到达。

总时间复杂度 $\mathcal O(nm)$。

代码

const int N = 1e3 + 7, M = 2e5 + 7;
int n, m, u[M], v[M];
bool w[N][N];
int p[N][N], q[N][N];
vi e[N];

void dfs(int x, bool *w) {
    w[x] = 1;
    for (int y : e[x])
        if (!w[y]) dfs(y, w);
}

void dfs(int x, int *p, int z) {
    p[x] = z;
    for (int y : e[x])
        if (!p[y]) dfs(y, p, z);
}

int main() {
    rd(n, m);
    for (int i = 1; i <= m; i++) rd(u[i], v[i]), e[u[i]].pb(v[i]);
    for (int x = 1; x <= n; x++) {
        dfs(x, w[x]);
        p[x][x] = q[x][x] = x;
        for (int y : e[x]) if (!p[x][y]) dfs(y, p[x], y);
        reverse(e[x].begin(), e[x].end());
        for (int y : e[x]) if (!q[x][y]) dfs(y, q[x], y);
    }
    for (int i = 1; i <= m; i++)
        prints((w[v[i]][u[i]] ^ (p[u[i]][v[i]] != q[u[i]][v[i]])) ? "diff" : "same");
    return 0;
}