自动搬运

查看原文

来自洛谷，原作者为

	dbxxx 多刷题，少整那些没用的

搬运于2025-08-24 22:42:48，当前版本为作者最后更新于2022-10-31 05:30:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

欢迎到我的博客中查看本文，谢谢！

修改日志：2023 年 7 月 7 日更改，添加一些说明。

先翻译一下题目：

$n$ 个点 $m$ 条边的有向图，每条边都有激活和失活两种状态，初始时均为激活状态。四种操作：

1. 失活某条边；
2. 失活以某个点为终点的所有边；
3. 激活某条边；
4. 激活以某个点为终点的所有边。

然后问：如果只考虑激活的边，是否满足：

• 所有的点出度均为 $1$；
• 所有的点都满足，从这个点出发，可以走到一个环中。

---

首先我们发现，如果所有点的出度均为 $1$，那么所有点都满足从这个点出发能走到一个环里。这是因为所有点的出度都是 $1$，因此一条路径可以一直走下去，而只要走 $n$ 步就一定会遇到先前走过的一个节点（总共只有 $n$ 个点），此时环就出现了。

因此压根不用判环，只用判断所有点出度是否均为 $1$。

事实上，所有点出度均为 $1$ 的有向图称作基环内向森林，它由若干个弱联通块（将所有有向边看成无向边后的联通块）构成，每个弱联通块称作基环内向树。对于基环内向树，它可以被认为是由有向环和长在环上的若干条链构成。这些链单向导通到环上。更多有关定义可以自行阅读 OI Wiki 的图论相关概念。

我们观察到，一、三操作可以用 $\mathcal{O}(1)$ 的效率修改一个点的出度（修改目标边的终点出度即可），而二、四操作只能用 $\mathcal{O}(n)$ 的效率（因为终点为 $v$ 的边有很多，对应的起点最多有 $n$ 个，它们的出度都需要被修改）。

不过，前 8 个测试点，是支持我们用最坏时间复杂度 $\mathcal{O}(nq)$ 的暴力维护出度的，所以 40 分已经到手。

然后 9 和 10 两个测试点还是保证没有二、四操作的。单次操作可以做到 $\mathcal{O}(1)$。因此这两个测试点用 $\mathcal{O}(q)$ 的复杂度解决，50 分到手。

这里是我的 50 分代码。

---

思考许久后我发现，容易维护的不是出度，而是入度。具体来说：

设原图上点 $u$ 的入度为 $g(u)$，当前点 $u$ 入度为 $r(u)$：

1. 失活 $(u, v)$：$r(v) \gets r(v) - 1$；
2. 失活以 $v$ 为终点的所有边：$r(v) \gets 0$；
3. 激活 $(u, v)$：$r(v) \gets r(v) + 1$；
4. 激活以 $v$ 为终点的所有边：$r(v) \gets g(v)$。

这些都可以 $\mathcal{O}(1)$ 完成。

那么入度和出度有什么关系呢？

一张图里，所有点的入度和等于出度和。我们的目标是所有出度都是 $1$，那么所有出度的和都是 $n$。因此入度的和也必须是 $n$。

于是我们得到所有出度均为 $1$ 的一个必要条件：入度和为 $n$。然而这个条件并不充分，因为入度和为 $n$ 可以推出出度和为 $n$，但不能再进一步推出所有出度均为 $1$。

比如，如果有三个点，点 $1$ 出度为 $2$，点 $2$ 出度为 $1$，点 $3$ 没有出度，我们如果单纯地去计算它的入度和，发现它等于 $n$，就判断现在每个点出度都是 $1$，这明显是错误的。

但是，我们可以利用 哈希 使得这个条件的充分性有极大概率是正确的，进一步使得这个条件的充要性极大概率正确，通过本题。

---

我们初始给每个点随机一个权值 $w(u)$。重新定义，一个点 $v$ 对应的 $r(v)$，表示直接连向 $v$ 的所有 $u$ 的 $w(u)$ 之和，即：

$$r(v) = \sum_{(u, v) \in E}w(u)$$

而 $g(v)$ 代表初始所有边都被激活时的 $r(v)$ 的值，且之后不改变（静态）。

重新设计：

1. 失活 $(u, v)$：$r(v) \gets r(v) - w(u)$；
2. 失活以 $v$ 为终点的所有边：$r(v) \gets 0$；
3. 激活 $(u, v)$：$r(v) \gets r(v) + w(u)$；
4. 激活以 $v$ 为终点的所有边：$r(v) \gets g(v)$。

这个过程中，所有点的 $r$ 值之和 $\sum r(u)$ 可以在每次操作时 $\mathcal{O}(1)$ 地维护。更进一步地：

• 设 $\{u_1, u_2, \ldots\}$ 是 $v$ 的入点集合，则 $r(v) = w(u_1) + w(u_2) + \ldots$。理由是 $r(v)$ 的定义。
• 如果所有点 $u$ 的出度都是 $1$，那么 $u$ 只会出现在它所连向的 $v$ 的入点集合中。因此，将所有入点集合的权值加起来，即 $\sum r(u)$，我们应该恰好得到 $\sum w(u)$。也即，$\sum r(u) = \sum w(u)$。

因此，$\sum r(u) = \sum w(u)$ 是每个点出度都为 $1$ 的一个必要条件。那么，这个条件充分吗？

一般地，我们设点 $u$ 的出度为 $k(u)$，意味着 $w(u)$ 恰好在最终的 $\sum r(u)$ 中出现 $k(u)$ 次。也即 $\sum r(u) = \sum k(u) \times w(u)$。因此我们可以将判断条件 $\sum r(u) = \sum w(u)$ 改写为：$\sum k(u) \times w(u) = \sum w(u)$。

显然所有 $k(u) = 1$ 是一个解。有其它的解吗？

有，但是这样的一组 $k$ 跟 $w$ 高度相关，除非出题人精心构造数据使得目前的局面形成的 $k$ 存在一个不等于 $1$ 还恰好满足这个方程，否则你可以认为当这个方程成立的时候，目前的 $k$ 都等于 $1$。

又因为你的 $w$ 是随机的，所以数据是没法对着你的代码卡的，除非你的 $w$ 正好随机到一个能把你代码卡掉的数据，这种可能太小了基本可以忽略不计，因为随机的值域已经相当大了。

这就是哈希的原理了：判定时构造一个必要不充分条件，但这个“不充分”实际上有非常大非常大的概率充分，以至于不充分性可以忽略不计，从而达到充要判定的效果。读者应当熟悉的字符串哈希，也是同样的原理。

这种哈希似乎一般称作“和哈希”（sum hash）。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-10-31 05:16:58 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-10-31 05:23:44
 */
#include <bits/stdc++.h>
#define int long long
inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}

const int maxn = (int)5e5 + 5;

int r[maxn], w[maxn], g[maxn];

signed main() {
    int n = read(), m = read();

    std :: mt19937 rng(time(0));
    
    for (int u = 1; u <= n; ++u)
        w[u] = rng(); // 这个函数生成随机数的范围和 unsigned int 范围一致，会爆 int。当然你也可以 % 一下
    
    int tar = std :: accumulate(w + 1, w + n + 1, 0LL);
    // 这是求和函数，注意 0 后面要加 LL （否则会爆）

    int now = 0;
    while (m--) {
        int u = read(), v = read();
        r[v] += w[u];
        g[v] = r[v];
        now += w[u];
    }

    int q = read();
    while (q--) {
        int t = read();
        if (t == 1) {
            int u = read(), v = read();
            r[v] -= w[u];
            now -= w[u];
        } else if (t == 2) {
            int v = read();
            now -= r[v];
            r[v] = 0;
        } else if (t == 3) {
            int u = read(), v = read();
            r[v] += w[u];
            now += w[u];
        } else if (t == 4) {
            int v = read();
            now += g[v] - r[v];
            r[v] = g[v];
        }

        puts(now == tar ? "YES" : "NO");
    }

    return 0;
}

如果觉得这篇题解写得好，请不要忘记点赞，谢谢！