29.并查集

发表于 更新于 分类于 ，

并查集

普通并查集与带权并查集，快速实现元素集合的合并与查询。

普通并查集

每个集合都有一些点，两个集合之间的任意点连接，则认为两个集合合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
集合A:    集合B:
  1         5
  |         |
  2         6---8
  |         |
  3         7---9
  |     
  4     

当2和6相连时，认为集合合并

  1         5
  |         |
  2 --------6---8
  |         |
  3         7---9
  |     
  4

此时想知道 \(4\) 和 \(8\) 是否在一个集合中，就不得不 DFS 一下，很费时间。

已在同个集合的两点不再连边，则每个集合都可以看作一个树形结构。

并查集通过路径压缩树变得"扁平"

1
2
3
4
5
6
7
      1             
    /   \           
   2     4               1
  /           ====>   / | | \  
3                    2  3 4  5    
  \                     
    5                   
1
2
3
4
5
6
7
8
9
10
11
12
void Init() {
    for(int i = 1; i <= n; i ++) {
        p[i] = i;   // 初始每个元素自己是一个集合
    }
}
// 找到 x 所在集合的树的根节点，同时进行路径压缩：
// 即 x 到根 路径上每个点都摘出来重新直接连到根节点上
int fa(int x) {return p[x] = x == p[x] ? x : fa(p[x]);}
void Join(int i, int j) {
    // 将 i 与 j 连接，即将它们所在的集合合并为一个
    p[fa(i)] = fa(j);
}

int fa(int x) {return p[x] = x == p[x] ? x : fa(p[x]);} 这行代码是并查集的精髓，拆解分析：

  • p[x] = 是在为 x 设置父节点，p[x]设为谁，谁就是x的直接父节点
  • x == p[x] ? 三元运算符，如果x自己就是p[x]，说明x是所在集合树的根节点
  • fa(p[x]) 如果 x != p[x]，则递归调用 fa(p[x]) ，即从 x 父节点继续向上递归找根节点
    • 这个递归会返回根节点，从而前面的 p[x] = 赋值就是根节点的编号
    • fa(p[x]) 会继续递归处理 x 的父节点 p[x]，那么 p[p[x]] 也会赋值为根节点，p[p[p[[x]]也会……
    • 从而完成路径压缩——x到根的一路的节点都把父节点设为了根节点

带权并查集

普通并查集的图，边只表示“是同一个集合”。而有一类表达关系的图，“边”带有关系属性。

例：食物链

有 \(N\) 个元素，编号为 \(1∼N\)。每个元素属于 \(A\)、\(B\)、\(C\) 三种类型之一（比如石头剪刀布），但具体类型未知。

给定 \(K\) 条信息，每条信息有两种形式：

  • \(1\) \(X\) \(Y\)：表示 \(X\) 和 \(Y\) 是同一类型
  • \(2\) \(X\) \(Y\)：表示 \(X\) 吃 \(Y\)（\(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)，形成环形）

判断这 \(K\) 条信息中有多少条是假信息。一条信息在以下情况下为假：

  • 与之前的信息冲突（\(A\)吃\(B\)，\(B\)吃\(C\)，但\(A\)又吃\(C\)，不符合循环，就是一种冲突）
  • \(X\) 或 \(Y\) 大于 \(N\)（出现了不存在的编号）
  • \(X\) 吃 \(X\)（自相矛盾）

输入：第一行 \(N\) \(K\)（\(N\) 个元素，\(K\) 条信息），接下来 \(K\) 行每行三个整数 \(D\) \(X\) \(Y\)（\(D\) 为 \(1\) 或 \(2\)）。

1
2
3
4
5
6
7
8
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

输出格式：一行，假信息的数量。

1
3

对于石头剪子布，\(X\)与\(Y\) 有 3 种边：\(X\) 吃 \(Y\)、\(Y\) 吃 \(X\)、\(X\)和\(Y\)同类，用集合表示“知道它们两两之间的关系”这个概念，还用这个图来理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
集合A:    集合B:
  1         5
  |         |
  2         6---8
  |         |
  3         7---9
  |     
  4     

当2和6相连时，认为集合合并

  1         5
  |         |
  2 --------6---8
  |         |
  3         7---9
  |     
  4

\(1,2,3,4\) 知道两两相克关系，\(5,6,7,8,9\) 知道两两相克关系，但是两个集合之间相克关系为止。

当某一刻告知了 \(2\) 吃 \(6\)，或 \(6\) 吃 \(2\)，或 \(2\) 与 \(6\) 同类，那么\(1\sim 9\) 的两两相克关系就全都能知道了。

这很像并查集的模型，但又不能简单地用父子节点的树来表达。需要让边带权，在路径压缩的时候也要压缩这个权值。

权值定义为：子节点与父节点的“顺时针”距离。

在石头剪子布里，距离就定义为：

  • 从石头到剪子、从剪子到布、从布到石头的距离都是 \(1\)
  • 从石头到布、从剪子到石头、从布道剪子的距离都是 \(2\)。

有这个顺时针距离，就可以确定相克关系。

路径压缩时，仍然是把树“扁平化”，因为维护了任意子节点到父节点的“食物链顺时针”距离，那么就可以压缩出节点到根节点的“食物链顺时针”距离。

用 \(A-B\) 表示计算从 \(B\) 出发到 \(A\) 的距离，来演练一下这个合并：

设 \(A\)、\(AR\) 是一个集合，\(AR\) 是根节点， \(B\)、\(BR\) 是一个集合，\(BR\) 是根节点。

1
2
3
4
5
    AR     BR
   /        \
 ...         ...
 /            \
A              B

当告知 \(A\) 与 \(B\) 的相克关系时，集合合并。先路径压缩，让\(A\)称为\(AR\)的直接子节点，\(B\) 也称为 \(BR\) 的直接子节点

1
2
3
  AR     BR
 /        \
A           B
1
2
3
4
5
6
int fa(int x) {
    int rt = x == p[x] ? x : fa(p[x]);
    d[x] = (d[x] + d[p[x]]) % 3;
    p[x] = rt;
    return rt;
}

代码中 p[x] 维护 x 的父节点， d[x] 维护 x到父节点的“食物链顺时针”距离。

当得知 \(A\) 与 \(B\) 相克关系时，进行类似合并集合操作，将 \(AR\) 作为 \(BR\) 的子节点：

1
2
3
4
5
    BR
   /  \
  AR   B
 /
A

$B-A = (B - BR) + (BR - AR) + (AR-A) $

这里 \(AR-A\) 就是代码中的 d[A]，BR-AR 是 d[AR]，BR-B（即-(B-BR)） 是 d[B]

因为集合合并是 将 \(AR\) 作为 \(BR\) 的子节点，所以在集合合并前后， \(A\)与\(B\) 的直接父节点不变（这一刻\(A\)暂且没有进一步路径压缩），从而d[A]、d[B]不变。

d[AR] 本来作为根节点是0，合并时只有它会变，要根据 \(A\)与\(B\) 的关系，在成为\(BR\) 的子节点后发生变化，变换之前的等式得到：

\((BR-AR) = (BR-B) - (AR-A) + (B-A)\)

对应代码中的 d[AR] = d[B] - d[A] + <A到B的食物链顺时针距离>

  • 当\(A\)与\(B\)是同类，则\(B-A=0\)，即 d[AR]= d[B] - d[A] + 0
  • 当 \(A\)吃\(B\)，则\(B-A=1\)，d[AR]= d[B] - d[A] + 1

从而集合基于 \(A\) 与 \(B\) 的关系合并，在两个集合各自路径压缩后，只需要 \(2\) 步：

  1. 把 \(AR\) 接到 \(BR\) 作为子节点，就是更新 p[AR]
  2. 确定 \(AR\) 到 \(BR\) 的距离，就是更新 d[AR]

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>
#include<cstdlib>
const int maxn = 5e4 + 10;
int p[maxn], d[maxn];
void Init() {
    for(int i = 0; i < maxn; i++) {
        p[i] = i;
        d[i] = 0;
    }
}
int fa(int x) {
    // 这里递归了，故p[x]往上已路径压缩
    int rt = x == p[x] ? x : fa(p[x]);  
    // 此时 d[p[x]] 已经是 p[x] 到 rt 的距离，那么 x 到 rt 的距离就是 d[x] + d[p[x]]
    d[x] = (d[x] + d[p[x]]) % 3;
    // 进行路径压缩，这里和并查集一样，把 x 作为 rt 的直接子节点
    p[x] = rt;
    return rt;
}
int main() {
    int N, K, fake = 0, op, a, b;
    scanf("%d%d", &N, &K);
    Init();
    while(K --) {
        scanf("%d%d%d", &op, &a, &b);
        if(a > N || b > N) {
            fake ++;
            continue;
        }
        if(op == 1) {
            if(fa(a) == fa(b) && d[a] != d[b]) {
                // 如果已是同一集合但 ab 并不是同类，矛盾
                // fa(a) == fa(b) 已经完成了路径压缩，d[a]和d[b]计算时都已是到同一个父节点的距离
                fake ++;
                continue;
            }
            // 此时 a 和 b 都已路径压缩了（在前面的if里）
            // a 祖先 ar 设为 b 祖先的子节点，更新 a 的祖先到 b 的祖先距离 d[ar]
            // 这里 a 和 b 同类，d[ar] 可根据公式推算，
            int ar = fa(a);    // 这里要暂存 fa(a)，避免后续合并时重复调用 fa(a) 出现错误
            p[ar] = fa(b);
            d[ar] = (d[b] - d[a] + 3) % 3;
        } else {
            if(fa(a) == fa(b) && (d[a] - d[b] + 3) % 3 != 1) {
                // 如果已是同一集合但 a 不吃 b，矛盾
                // a 吃 b 即 a 到 b “食物链顺时针”距离为 1， +3 补足 %3 的同余避免出现负数
                // a 到 b 的距离，即 b - a = (ar - a) - (br - b) = d[a] - d[b]
                fake ++;
                continue;
            }
            // 原理同上
            int ar = fa(a);
            // 这里 +4 而不是 +1，是补足 %3 的同余避免出现负数，正确计算“食物链顺时针”距离
            p[ar] = fa(b);
            d[ar] = (d[b] - d[a] + 4) % 3;  
        }
    }
    printf("%d\n", fake);
    return 0;
}