并查集的高级用法——权值并查集与种类并查集

并查集#

并查集，或称DSUDisjoint Set Union，是一种管理元素所属集合的数据结构。每次查询时把沿途的节点的父节点一并设置成全局父节点，从而达到均摊复杂度 $\mathcal O(\alpha(n))$ 的超高效率（其中 $\alpha(n)$ 为 $n$ 的反阿克曼函数，可以看作为常数复杂度）。基于并查集的许多特性（包括好写），人们开发出了许多不同种类不同用途的并查集，其中就包括带边权的权值并查集和对元素进行分类的种类并查集。这篇文章将探讨这两种并查集的实现及相关应用。

权值并查集#

在并查集的边上加上边权，每次查找父节点时把边权向上推送更新，从而达到类似于线段树 pushup 操作的效果。

UVA 11987 Almost Union-Find#

题目地址：UVA 11987

题目难度：提高+/省选-

有 $n$ 个集合， $m$ 次操作。规定第 $i$ 个集合里初始只有 $i$ 。有三种操作：

输入两个元素 $p$ 和 $q$ ，若 $p$ 和 $q$ 不在一个集合中，合并两个元素的集合。

输入两个元素 $p$ 和 $q$ ，若 $p$ 和 $q$ 不在一个集合中，把 $p$ 添加到 $q$ 所在的集合。

输入一个元素 $p$ ，查询 $p$ 所在集合的元素个数和所有元素之和。

输入格式：
有几组数据。
每组数据第一行输入 $n$ 和 $m$ 两个整数。
每组数据以下 $m$ 行，每行第一个数 $k$ 代表选择哪一个命令，若 $k$ 是 $1$ 或 $2$ 命令，则再输入两个整数 $p$ 和 $q$ 。若 $k$ 是 $3$ ，则输入一个整数 $p$ 。
输入文件结束符（EOF）结束输入。
输出格式：
输出行数为每组数据 $3$ 号命令的总数。
每一行输出两个整数 $a$ 和 $b$ ，即元素个数和元素和。
数据范围：
${1 \leq n,m\leq 10 ^ 5}$ ， ${1 \leq p,q\leq n}$ 。
原题面 PDF：Here

这道题在普通并查集维护所属集合的要求外，另外要求我们维护并查集的集合大小及元素总和，因此考虑权值并查集。基本思路是：在每次合并操作时，更新被插入集合父节点的 sum 与 size，累加上待插入集合的 sum 与 size 即可。特殊一点，对于移动操作（相当于把待插入集合变成一个大小为 ${1}$ 的单点）也是一样。

那么如何实现单点的移动呢？一般的思路是把点的父亲直接指向被插入集合的根，但这显然是错误的，因为：

当我们根据并查集的标准合并方式合并节点 ${1}$ 到树 ${3}$ 时，我们会把从属于 ${1}$ 号的 ${2}$ 号节点也一并接过去，这是我们不希望的，期望效果是只把 ${1}$ 送过去，只留下 ${2}$ 号一个在原位置。

那我们就需要提出一种建图方式，使得 ${2}$ 不直接与 ${1}$ 相连，但是要求 ${2}$ 又属于 ${1}$ 树。考虑为每个集合设置虚拟源点，初始时每个集合就是以虚拟源点为根，普通节点为叶子的两点集合。如此一来，移动操作就变成了下图：

然后就可以按照普通并查集的方法解了（因为创建了 $n$ 个虚拟源点，空间要开二倍）。

1
#include <bits/stdc++.h>
2

3
#define N 200010
4

5
using namespace std;
6

7
typedef long long ll;
8

9
int p[N], vol[N];
10
ll sum[N];
11

12
int find(int x) {
13
    if (p[x] != x) p[x] = find(p[x]);
14
    return p[x];
15
}
16

17
void merge(int a, int b) {
18
    int u = find(a), v = find(b);
19
    p[u] = v;
20
    sum[v] += sum[u];
21
    vol[v] += vol[u];
22
}
23

24
void move(int a, int dest) {
25
    int u = find(a), v = find(dest);
26
    p[a] = v;
27
    vol[v]++;
28
    vol[u]--;
29
    sum[u] -= a;
30
    sum[v] += a;
31
}
32

33
bool related(int a, int b) {
34
    return find(a) == find(b);
35
}
36

37
int main() {
38
    ios::sync_with_stdio(false);
39
    cin.tie(nullptr);
40
    cout.tie(nullptr);
41

42
    int n, m;
43
    while (cin >> n >> m) {
44
        for (int i = 1; i <= 2 * n; i++) {
45
            if (i <= n) {
46
                p[i] = i + n;
47
                vol[i] = 1;
48
                sum[i] = i;
49
            } else if (i > n) {
50
                p[i] = i;
51
                vol[i] = 1;
52
                sum[i] = i - n;
53
            }
54
        }
55
        while (m--) {
56
            int k, a, b;
57
            cin >> k;
58
            if (k == 1) {
59
                cin >> a >> b;
60
                if (!related(a, b)) merge(a, b);
61
            } else if (k == 2) {
62
                cin >> a >> b;
63
                if (!related(a, b)) move(a, b);
64
            } else {
65
                cin >> a;
66
                int u = find(a);
67
                cout << vol[u] << ' ' << sum[u] << endl;
68
            }
69
        }
70
    }
71
    return 0;
72
}

练习：P1196 [NOI2002] 银河英雄传说

种类并查集#

一般的并查集可以用来维护一个带有传递性和连通性的集合，例如你亲戚的亲戚仍然是你的亲戚，普通并查集就可以做到维护你的所有亲戚和非亲戚，并判断某人是否是你的亲戚；而种类并查集则是它的升级，普通的并查集显然无法轻易维护诸如“敌人的敌人是朋友”的人际关系。这时，我们就可以多开几个普通的并查集用来维护不同类别之间的关系，即种类并查集。

P2024 [NOI2001] 食物链#

题目地址：P2024

题目难度：普及+/提高

题目来源：NOI 2001

动物王国中有三类动物 $A,B,C$ ，这三类动物的食物链构成了有趣的环形。 $A$ 吃 $B$ ， $B$ 吃 $C$ ， $C$ 吃 $A$ 。
现有 $N$ 个动物，以 ${1 \sim N}$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。

第二种说法是2 X Y，表示 $X$ 吃 $Y$ 。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话；

当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；

当前的话表示 $X$ 吃 $X$ ，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。
输入格式：
第一行两个整数， $N,K$ ，表示有 $N$ 个动物， $K$ 句话。
第二行开始每行一句话（按照题目要求，见样例）
输出格式：
一行，一个整数，表示假话的总数。
数据范围：
对于全部数据， ${1\le N\le 5 \times 10^4}$ ， ${1\le K \le 10^5}$ 。

这道题是种类并查集的经典应用之一，用来判断一个不等式组是否有冲突矛盾。之前在讲Floyd 传递闭包的时候，我们就介绍了用传递闭包求解不等式组解的情况的方法。但是这种基于 $\texttt{Floyd}$ 算法的解法，其时间复杂度是恐怖的 $\mathcal O(n^3)$ ，在这道题里显然会超时，我们转而使用种类并查集来解决这道题。

整理一下题面，把这些动物分成三类——“国王”、“大臣”和“平民”。国王统治大臣、大臣压榨平民、平民推翻国王。但是关键是我们不知道动物的初始分类，因此我们在每一类里都放上 $n$ 个节点。

然后，对于操作 ${1}$ ——可能出现的矛盾是：二者不为同类，这里却归为同类；对于操作 ${2}$ ，可能出现的是：倒反天罡（大臣搞国王、平民踩大臣）、自残（自己吃自己）。换句话说，如果某个节点的根指到其他区域，那么这两个动物在当前信息下不可能成为同类；如果不满足镇压关系的二者共用同一个根，显然也不成立。

根据并查集所带的实际意义判断即可。注意如果当前命题是正确的，不要忘记合并到并查集里。

1
#include <bits/stdc++.h>
2

3
#define N 50010
4
using namespace std;
5

6
int p[N * 3];
7
int n;
8

9
int find(int x) {
10
    if (p[x] != x) p[x] = find(p[x]);
11
    return p[x];
12
}
13

14
void merge(int a, int b) {
15
    p[find(a)] = find(b);
16
}
17

18
bool related(int a, int b) {
19
    return find(a) == find(b);
20
}
21

22
int main() {
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25
    cout.tie(nullptr);
26

27
    int k, ans = 0;
28
    cin >> n >> k;
29
    for (int i = 1; i <= 3 * n; i++) p[i] = i;
30
    while (k--) {
31
        int op, x, y;
32
        cin >> op >> x >> y;
33
        if (x > n || y > n) ans++;
34
        else if (op == 1) {
35
            if (related(x + n, y) || related(x, y + n)) ans++;
36
            else {
37
                merge(x, y);
38
                merge(x + n, y + n);
39
                merge(x + 2 * n, y + 2 * n);
40
            }
41
        } else {
42
            if (related(x, y) || related(x, y + n)) ans++;
43
            else {
44
                merge(x, y + 2 * n);
45
                merge(x + n, y);
46
                merge(x + 2 * n, y + n);
47
            }
48
        }
49
    }
50
    cout << ans << endl;
51
    return 0;
52
}

练习：P1955 [NOI2015] 程序自动分析

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

并查集的高级用法——权值并查集与种类并查集

并查集#

权值并查集#

UVA 11987 Almost Union-Find#

种类并查集#

P2024 [NOI2001] 食物链#

支持与分享

评论区

音乐

目录

音乐

JustPureH2O

穷方圆平直之情，尽规矩准绳之用

音乐

并查集的高级用法——权值并查集与种类并查集

并查集#

权值并查集#

UVA 11987 Almost Union-Find#

种类并查集#

P2024 [NOI2001] 食物链#

支持与分享

评论区

音乐

目录

JustPureH₂O