Link

51nod 1470

Sol

不错的题目

拿到题目感觉没啥想法,但是仔细想想,会发现切入点应该是什么样的边如何影响有没有解。

假如有一个环,定向以后仍然环上的点仍然可以互相到达。那么环是我们可以不需要考虑合不合法的因素。推广一下,在一个 e-DDC 中的点给边定向以后也是都可以互相到达的。因此,可以先对原图进行 e-DDC 缩边,得到了一棵原图中桥组成的树。

现在影响是否有解的只有这棵树上的边了。相当于我们要给树边定向。我们钦定对于一个限制 $(s, t)$,$p$ 为 $s,t$ 对应的 e-DDC 的树上结点的 LCA。从 $s \to p$ 的为正向,从 $v \to p$ 的为反向。那么可以把 $s \to p$ 的路径上的点全部 $+1$,$t \to p$ 的全部 $-1$。只需要检查有没有一个点的权值为 $0$ 即可。

如果你想多一个 $\log$,可以选择线段树。但是只需要树上差分就行了。

Code

#include <bits/stdc++.h>
using namespace std;

typedef vector < int > vec;
const int SIZE = 5e5 + 5;

int n, m, q, num = 1, tim, cnt, N;
int head[SIZE], dfn[SIZE], low[SIZE], bri[SIZE], deg[SIZE], col[SIZE];
int dep[SIZE], idx[SIZE], bel[SIZE], fa[SIZE], siz[SIZE], son[SIZE], dif1[SIZE], dif2[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];
vec g[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

void addEdge(int u, int v) {
    edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void dfs(int u, int p) {
    dfn[u] = low[u] = ++ tim;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (!dfn[v]) {
            dfs(v, i);
            low[u] = std::min(low[u], low[v]);
            if (low[v] > dfn[u]) bri[i] = bri[i ^ 1] = 1;
        }
        else if (i != (p ^ 1)) low[u] = std::min(low[u], dfn[v]);
    }
}

void ddc(int u) {
    col[u] = cnt;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (col[v] || bri[i]) continue;
        ddc(v);
    }
}

void dfs0(int u, int anc) {
    siz[u] = 1, idx[u] = N;
    for (int v: g[u]) {
        if (v == anc) continue;
        fa[v] = u, dep[v] = dep[u] + 1; dfs0(v, u); siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void dfs1(int u, int top) {
    bel[u] = top;
    if (son[u]) dfs1(son[u], top);
    for (int v: g[u]) {
        if (v == son[u] || v == fa[u]) continue;
        dfs1(v, v);
    }
}

int lca(int u, int v) {
    while (bel[u] ^ bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        u = fa[bel[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

int judge(int u) {
    for (int v: g[u]) {
        if (v == fa[u]) continue;
        if (!judge(v) || (dif1[v] && dif2[v])) return 0;
        dif1[u] += dif1[v], dif2[u] += dif2[v];
    }
    return 1;
}

int main() {
    // freopen("code.in", "r", stdin);
    n = read(), m = read(), q = read();
    for (int i = 1, u, v; i <= m; ++ i) {
        u = read(), v = read();
        addEdge(u, v), addEdge(v, u);
    }
    for (int i = 1; i <= n; ++ i)
        if (!dfn[i]) dfs(i, 0);
    for (int i = 1; i <= n; ++ i) {
        if (!col[i]) { ++ cnt; ddc(i); }
    }
    for (int u = 1; u <= n; ++ u) {
        for (int i = head[u], v; i; i = edge[i].nxt) {
            v = edge[i].to;
            if (col[u] < col[v]) {
                g[col[u]].emplace_back(col[v]), 
                g[col[v]].emplace_back(col[u]);
            }
        }
    }
    for (int i = 1; i <= cnt; ++ i) {
        if (!idx[i]) {
            dep[i] = 0, fa[i] = 0, idx[i] = ++ N;
            dfs0(i, 0), dfs1(i, 1);
        }
    }
    for (int i = 1, u, v; i <= q; ++ i) {
        u = col[read()], v = col[read()];
        if (u == v) continue;
        if (idx[u] != idx[v]) return puts("No"), 0;
        int par = lca(u, v);
        -- dif1[par], -- dif2[par]; ++ dif1[u], ++ dif2[v];
    }
    for (int i = 1; i <= cnt; ++ i) {
        if (dep[i] == 0 && !judge(i)) return puts("No"), 0;
    }
    puts("Yes");
    return 0;
}
最后修改:2021 年 09 月 24 日
如果觉得我的文章对你有用,请随意赞赏