并查集专题复习笔记

并查集专题复习笔记#

0. 总览#

并查集这一章在课程 PPT 中的主线是：

1. Equivalence Relations：等价关系、等价类。
2. Dynamic Equivalence Problem：动态判断两个元素是否等价。
3. Basic Data Structure：用森林和数组表示 disjoint sets。
4. Smart Union Algorithms：union-by-size 和 union-by-height/rank。
5. Path Compression：路径压缩。
6. Worst Case：union-by-rank + path compression 的反 Ackermann 复杂度。

复习时抓住一句话：并查集维护的是“集合划分”，核心操作只有两个：

• Find(x)：找到元素 \(x\) 所在集合的代表元。
• Union(a, b)：把两个集合合并成一个集合。

在题目里它常被包装成“连通性”“朋友圈/社交簇”“网络是否连通”“等价类合并”等问题。

1. Equivalence Relations#

1.1 Relation#

课程 PPT 的定义：

A relation $R$ is defined on a set $S$ if for every pair of elements $(a, b)$, $a, b \in S$, $aRb$ is either true or false.

也就是说，关系 $R$ 是定义在集合 $S$ 上的一种判断规则。对任意两个元素 $a, b$，命题 $aRb$ 要么为真，要么为假。

如果 $aRb$ 为真，就说：

a is related to b

1.2 Equivalence Relation#

课程 PPT 的定义：

A relation, $\sim$, over a set $S$, is said to be an equivalence relation over $S$ iff it is symmetric, reflexive, and transitive over $S$.

等价关系必须满足三条性质：

这三条性质决定了等价关系会把原集合切分成若干个互不相交的小集合。

1.3 Equivalence Class#

课程 PPT 的定义：

Two members $x$ and $y$ of a set $S$ are said to be in the same equivalence class iff $x \sim y$.

如果 $x \sim y$，则 $x$ 和 $y$ 在同一个等价类里。

例如：

S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }

给定 9 个关系：

12 == 4, 3 == 1, 6 == 10, 8 == 9, 7 == 4,
6 == 8, 3 == 5, 2 == 11, 11 == 12

最后得到的等价类是：

{ 2, 4, 7, 11, 12 }
{ 1, 3, 5 }
{ 6, 8, 9, 10 }

注意：并查集不关心集合内元素的顺序，只关心“谁和谁属于同一个集合”。

2. Dynamic Equivalence Problem#

2.1 问题描述#

课程 PPT 的说法：

Given an equivalence relation $\sim$, decide for any $a$ and $b$ if $a \sim b$.

目标是动态处理两类操作：

1. 输入一个关系 $a \sim b$，把 $a$ 和 $b$ 所在集合合并。
2. 查询任意两个元素 $a$ 和 $b$ 是否在同一个等价类中。

这就是 dynamic equivalence problem。

“Dynamic / on-line” 的意思是：关系和查询不是一次性全部算好，而是一边读入操作，一边维护当前状态。

2.2 基本算法框架#

PPT 中给出的算法思想：

Initialize N disjoint sets;

while (read in a ~ b) {
    if (!(Find(a) == Find(b)))
        Union the two sets;
}

while (read in a and b) {
    if (Find(a) == Find(b))
        output(true);
    else
        output(false);
}

核心判断：

Find(a) == Find(b)

如果两个元素的代表元相同，说明它们在同一个集合里。

2.3 Disjoint Sets#

PPT 对集合的设定：

Elements: 1, 2, 3, ..., N
Sets: S1, S2, ...
Si ∩ Sj = empty, if i != j

也就是说：

• 每个元素属于且只属于一个集合。
• 不同集合之间没有公共元素。
• 初始时通常令每个元素自成一个集合：$S_i = \{i\}$。

例如：

S1 = { 6, 7, 8, 10 }
S2 = { 1, 4, 9 }
S3 = { 2, 3, 5 }

3. Basic Data Structure#

3.1 Forest Representation#

并查集通常用森林表示每个集合：

• 每个集合是一棵树。
• 树根作为这个集合的代表元。
• 指针方向从 child 指向 parent。
• 根结点没有父亲。

PPT 特别强调：

Pointers are from children to parents.

这和普通树里常画的 parent-to-children 方向相反。这里这么做是为了让 Find(x) 可以从元素一路向上找到根。

3.2 Union#

课程 PPT 的定义：

Union(i, j) ::= Replace Si and Sj by S = Si ∪ Sj

思想：

Make $S_i$ a subtree of $S_j$, or vice versa.

也就是把一棵树的根挂到另一棵树的根下面。

基础版本：

void SetUnion(DisjSet S, SetType Rt1, SetType Rt2) {
    S[Rt2] = Rt1;
}

这里默认 Rt1 和 Rt2 已经是两个集合的根。实际写代码时，常见写法是：

int r1 = Find(x, S);
int r2 = Find(y, S);

if (r1 != r2)
    S[r2] = r1;

3.3 Find#

课程 PPT 的定义：

Find(i) ::= Find the set Sk which contains the element i.

如果使用数组 \(S[element] = element's parent\)，则：

• \(S[x] > 0\)：S[x] 是 \(x\) 的父结点。
• \(S[root] = 0\)：root 是根，集合名就是根的编号。

PPT 中的基础 Find：

SetType Find(ElementType X, DisjSet S) {
    for (; S[X] > 0; X = S[X])
        ;
    return X;
}

这个版本会沿着父指针不断向上走，直到找到根。

3.4 两种实现思路#

PPT 里区分了两种实现：

课程后续主要使用 Implementation 2，也就是 parent array。

原因是元素编号为 1..N：

the elements are numbered from 1 to N. Hence they can be used as indices of an array.

所以 C 语言中可以直接用数组表示：

int S[N + 1];

通常下标 0 不用，元素从 1 到 \(N\)。

4. Smart Union Algorithms#

普通 Union 的问题是：如果总是随便把一棵树挂到另一棵树下面，树可能退化成一条长链，Find 最坏会变成 $O(N)$。

Smart union 的目标是让树尽量矮。

4.1 Union-by-Size#

PPT 的原则：

Always change the smaller tree.

也就是把小树挂到大树下面。

课程 PPT 中的数组约定：

S[Root] = -size;  /* initialized to be -1 */

含义：

• 如果 \(S[x] < 0\)，则 \(x\) 是根。
• -S[x] 表示这棵树的结点数。
• 初始时每个集合只有一个元素，所以 \(S[i] = -1\)。

合并时：

if (S[root1] < S[root2]) {
    /* root1 的集合更大，因为负数更小 */
    S[root1] += S[root2];
    S[root2] = root1;
} else {
    S[root2] += S[root1];
    S[root1] = root2;
}

注意这个比较很容易写反：

• S[root] 是负数。
• S[root] 越小，集合越大。
• 例如 \(-8 < -3\)，所以 -8 对应的集合更大。

4.2 Union-by-Size 的高度界#

课程 PPT 的 lemma：

Let $T$ be a tree created by union-by-size with $N$ nodes.

结论是树高最多是 $O(\log N)$。

直观证明：

1. 一个结点的深度只有在它所在的树被挂到另一棵树下面时才会增加。
2. union-by-size 只会把小树挂到大树下面。
3. 所以每当某个结点深度增加 1，它所在集合的大小至少翻倍。
4. 一个集合最多长到 $N$，所以一个结点的深度最多增加 $\log_2 N$ 次。

因此使用 union-by-size 后，Find 的最坏复杂度从 $O(N)$ 降到 $O(\log N)$。

课程 PPT 给出的序列复杂度：

N Union and M Find operations: O(N + M log2 N)

4.3 Union-by-Height / Union-by-Rank#

PPT 的原则：

Always change the shallow tree.

也就是把较矮的树挂到较高的树下面。

常见实现会把根的高度或 rank 存在根结点中：

• 高度小的根挂到高度大的根下面。
• 高度相等时，任选一个作为新根，并把新根的 rank 加 1。

路径压缩加入后，真实高度会被改变，所以通常不再把它理解为准确 height，而是把它当成估计用的 rank。

5. Path Compression#

5.1 思想#

路径压缩的核心是：

做 Find(x) 时，不只找到根，还顺手把路径上的结点都直接挂到根下面。

这样一次 Find 可能比普通版本稍慢，但之后同一条路径上的查询会快很多。

PPT 的说明：

Slower for a single find, but faster for a sequence of find operations.

5.2 递归版 Path Compression#

PPT 中的递归版本：

SetType Find(ElementType X, DisjSet S) {
    if (S[X] <= 0)
        return X;
    else
        return S[X] = Find(S[X], S);
}

关键语句：

S[X] = Find(S[X], S);

它同时完成两件事：

1. 递归找到根。
2. 回溯时把 \(X\) 的父亲直接改成根。

如果采用 \(S[root] = -size\) 的写法，根的判断条件就是：

S[X] <= 0

或者更常见地写成：

S[X] < 0

具体取决于根结点用 0 还是负数表示。

5.3 非递归版 Path Compression#

PPT 中的非递归版本：

SetType Find(ElementType X, DisjSet S) {
    ElementType root, trail, lead;

    for (root = X; S[root] > 0; root = S[root])
        ;  /* find the root */

    for (trail = X; trail != root; trail = lead) {
        lead = S[trail];
        S[trail] = root;
    }  /* collapsing */

    return root;
}

它分两步：

1. 第一段循环找到根 root。
2. 第二段循环从原来的 \(X\) 出发，把路径上的每个结点都改为直接指向 root。

5.4 与 Union-by-Height 的关系#

PPT 的提醒：

Not compatible with union-by-height since it changes the heights.
Just take "height" as an estimated rank.

意思是：

• 路径压缩会改变树的真实高度。
• 如果你还维护一个字段叫 height，它不再是真实高度。
• 但可以把它当作 rank，用来近似指导合并方向。

所以常见组合是：

union-by-rank + path compression

而不是严格意义上的“真实高度 + path compression”。

6. Worst Case Complexity#

6.1 Tarjan Lemma#

课程 PPT 给出的结论：

Let $T(M, N)$ be the maximum time required to process an intermixed sequence of $M \ge N$ finds and $N - 1$ unions.

则：

其中 $k_1, k_2$ 是正常数，$\alpha(M, N)$ 是反 Ackermann 函数。

复习时不需要展开 Ackermann 函数的完整定义，记住考试常用结论即可：

union-by-rank + path compression 的摊还复杂度几乎是常数

更具体地说，单次操作的摊还复杂度常写作：

在实际数据范围内，$\alpha(N)$ 增长极慢，可以近似看成不超过一个很小的常数。

6.2 log star#

PPT 还提到：

alpha(M, N) <= O(log* N) <= 4

其中 \(\log* N\) 表示不断对 $N$ 取对数，直到结果 $\le 1$ 所需的次数。

PPT 示例：

log* 2^65536 = 5

因为：

log log log log log (2^65536) = 1

这说明这些函数增长极慢。并查集的复杂度分析看起来很高级，但写题时通常只需要知道：

• 不优化：最坏可能 $O(N)$。
• union-by-size/rank：$O(\log N)$。
• 再加 path compression：摊还近似 $O(1)$。

7. 课程代码：File Transfer#

仓库里的实现文件：

w7_union_and_find/filetransfer.c

这是一个典型的并查集连通性问题。

7.1 操作含义#

常见输入命令：

判断网络是否连通：

• 如果只有一个根，说明所有结点属于同一个集合。
• 如果有多个根，根的数量就是 connected components 的数量。

7.2 初始化#

代码使用负数表示集合大小：

void init(int *set, int n) {
    for (int i = 1; i < n + 1; i++) {
        set[i] = -1;
    }
}

含义：

• 初始时每个结点自成一个集合。
• 每个集合大小为 1。
• 根结点存储 -1。

7.3 Find：路径压缩#

代码中的 find：

int find(int ele, int *set) {
    if (set[ele] < 0)
        return ele;
    else
        return set[ele] = find(set[ele], set);
}

这是递归版 path compression。

如果 \(set[ele] < 0\)，说明 ele 是根；否则继续向父结点查找，并把 ele 直接挂到根下面。

7.4 Union：按大小合并#

代码中的 \(my_{union}\)：

void my_union(int e1, int e2, int *set) {
    int s1 = find(e1, set), s2 = find(e2, set);

    if (s1 == s2)
        return;

    if (set[s1] < set[s2]) {
        set[s1] += set[s2];
        set[s2] = s1;
    } else {
        set[s2] += set[s1];
        set[s1] = s2;
    }
}

这里 set[root] 是负数，所以：

set[s1] < set[s2]

表示 \(s_{1}\) 所在集合更大。

例如：

set[s1] = -5
set[s2] = -2

则 \(s_{1}\) 的集合大小是 5，\(s_{2}\) 的集合大小是 2，应当把 \(s_{2}\) 挂到 \(s_{1}\) 下。

合并后的更新：

set[s1] += set[s2];  /* 新 size = 5 + 2，只是用负数存，所以是 -7 */
set[s2] = s1;        /* s2 不再是根，父亲变成 s1 */

7.5 统计 connected components#

代码中判断网络是否连通：

int num_of_connect = 0;
for (int i = 1; i < N + 1; i++) {
    if (disjset[i] < 0) {
        num_of_connect++;
    }
}

因为只有根结点的值是负数，所以统计负数个数就等于统计集合个数。

输出逻辑：

if (num_of_connect == 1)
    printf("The network is connected.\n");
else
    printf("There are %d components.", num_of_connect);

8. 常用模板#

8.1 负 size + path compression + union-by-size#

这是本课程代码最常用的写法：

void Init(int S[], int N) {
    for (int i = 1; i <= N; i++)
        S[i] = -1;
}

int Find(int x, int S[]) {
    if (S[x] < 0)
        return x;
    return S[x] = Find(S[x], S);
}

void Union(int a, int b, int S[]) {
    int r1 = Find(a, S);
    int r2 = Find(b, S);

    if (r1 == r2)
        return;

    if (S[r1] < S[r2]) {
        S[r1] += S[r2];
        S[r2] = r1;
    } else {
        S[r2] += S[r1];
        S[r1] = r2;
    }
}

8.2 如果根用 0 表示#

PPT 的基础版本中也出现过：

S[root] = 0

此时 Find 判断根的条件通常写成：

while (S[x] > 0)
    x = S[x];

或者：

if (S[x] <= 0)
    return x;

但如果根用 0 表示，就不能同时在根里保存集合大小。要做 union-by-size，需要另外开一个 size[] 数组。

9. 易错点#

9.1 Union(a, b) 前必须先找根#

错误写法：

S[b] = a;

如果 \(a\) 或 \(b\) 不是根，这样会破坏集合结构。

正确做法：

int r1 = Find(a, S);
int r2 = Find(b, S);
S[r2] = r1;

9.2 负数 size 的比较方向#

如果根里存的是 -size：

-10 < -3

所以值更小的根，集合反而更大。

写 union-by-size 时要特别注意：

if (S[r1] < S[r2])
    r1 is larger;
else
    r2 is larger or equal;

9.3 查询时比较代表元#

判断两个元素是否在同一集合：

Find(a, S) == Find(b, S)

不要直接写：

S[a] == S[b]

因为两个结点可能父亲不同，但根相同。

9.4 component 个数等于根的个数#

如果使用 \(S[root] < 0\) 表示根，则 connected components 个数为：

int count = 0;
for (int i = 1; i <= N; i++)
    if (S[i] < 0)
        count++;

路径压缩不会改变根的负数标记，所以这个统计方法仍然有效。

9.5 下标范围#

本课程 PPT 假设元素编号为：

1, 2, 3, ..., N

因此数组通常开：

int S[N + 1];

循环用：

for (int i = 1; i <= N; i++)

不要误把 0 当作有效元素，除非题目明确说元素从 0 开始编号。

10. 复习速记#

一句话模板：

并查集用 parent array 表示一组互不相交的集合；
Find 沿父指针找根，Union 合并两个根；
用 union-by-size/rank 控制树高，用 path compression 加速后续查询。