Visits: 234

CF555E Case of Computer Network

题意

• 给定一张 $n$ 个点 $m$ 条边的无向图。
• 给定 $q$ 组有向点对 $(s, t)$。
• 询问是否存在使得所有 $s$ 都能到达 $t$ 的无向图中每条边的定向方案。
• $n,m,q \le 2 \times 10^5$。

题解

先求边双，缩点变成森林。

判定时先求 lca，树上差分一下即可，时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 2e5 + 7;
int n, m, q;
int h[N], e[N<<1], t[N<<1], p = 1;
int dfn[N], low[N], num;
int b[N<<1], c[N], k;
int hc[N], ec[N<<1], tc[N<<1], pc = 1;
int v[N], w, f[N][20], d[N], g1[N], g2[N];

inline void add(int x, int y, int z = 1) {
    e[++p] = y;
    t[p] = h[x];
    h[x] = p;
    if (z) add(y, x, 0);
}

void tarjan(int x, int f) {
    dfn[x] = low[x] = ++num;
    for (int i = h[x]; i; i = t[i]) {
        if (i == f) continue;
        int y = e[i];
        if (dfn[y]) low[x] = min(low[x], dfn[y]);
        else {
            tarjan(y, i ^ 1), low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x]) b[i] = b[i^1] = 1;
        }
    }
}

void dfs(int x) {
    c[x] = k;
    for (int i = h[x]; i; i = t[i]) {
        if (b[i]) continue;
        int y = e[i];
        if (c[y]) continue;
        dfs(y);
    }
}

inline void addc(int x, int y, int z = 1) {
    ec[++pc] = y;
    tc[pc] = hc[x];
    hc[x] = pc;
    if (z) addc(y, x, 0);
}

void dfsc(int x) {
    v[x] = w;
    for (int i = hc[x]; i; i = tc[i]) {
        int y = ec[i];
        if (y == f[x][0]) continue;
        f[y][0] = x, d[y] = d[x] + 1;
        for (int j = 0; f[y][j]; j++)
            f[y][j+1] = f[f[y][j]][j];
        dfsc(y);
    }
}

inline int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i = 19; ~i; i--)
        if (d[f[y][i]] >= d[x]) y = f[y][i];
    if (x == y) return x;
    for (int i = 19; ~i; i--)
        if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

bool dfspd(int x) {
    for (int i = hc[x]; i; i = tc[i]) {
        int y = ec[i];
        if (y == f[x][0]) continue;
        if (!dfspd(y) || (g1[y] && g2[y])) return 0;
        g1[x] += g1[y], g2[x] += g2[y];
    }
    return 1;
}

int main() {
    rd(n), rd(m), rd(q);
    for (int i = 1, x, y; i <= m; i++)
        rd(x), rd(y), add(x, y);
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);
    for (int i = 1; i <= n; i++)
        if (!c[i]) ++k, dfs(i);
    for (int x = 1; x <= n; x++)
        for (int i = h[x]; i; i = t[i]) {
            int y = e[i];
            if (c[x] >= c[y]) continue;
            addc(c[x], c[y]);
        }
    for (int i = 1; i <= k; i++)
        if (!v[i]) ++w, d[i] = 1, dfsc(i);
    for (int i = 1, x, y; i <= q; i++) {
        rd(x), rd(y), x = c[x], y = c[y];
        if (x == y) continue;
        if (v[x] != v[y]) return prints("No"), 0;
        int z = lca(x, y);
        ++g1[x], --g1[z], ++g2[y], --g2[z];
    }
    for (int i = 1; i <= n; i++)
        if (d[i] == 1 && !dfspd(i)) return prints("No"), 0;
    prints("Yes");
    return 0;
}