并查集

并查集（Union-Find Set，Disjoint Set Union，DSU）是一种处理不相交集合的合并与查询问题的数据结构。它特别适合解决这类问题：

两个元素是否属于同一个集合
动态合并两个集合
图中的连通性问题

常见应用包括：朋友圈数量、岛屿数量、冗余连接、Kruskal 最小生成树。

1. 核心概念

并查集支持三种基本操作：

Initial(S)：初始化，把每个元素都看成一个单元素集合。
Union(S, Root1, Root2)：把两个不同集合合并成一个集合。
Find(S, x)：查找元素 x 所属集合的根结点。

可以把每个集合看成一棵树，多个集合组成一个森林。每棵树的根代表一个集合。

2. 存储结构

并查集常用双亲数组来存储森林结构。设数组为 S：

若 S[i] < 0，说明 i 是根结点。
若 S[i] >= 0，说明 S[i] 存的是 i 的父结点下标。

在优化版实现里，根结点位置保存的不只是“它是根”，还会顺便记录集合规模：

S[i] = -size：表示 i 是根，且该集合有 size 个元素。

初始化示意

设全集为 S = {0,1,2,3,4,5,6,7,8,9}，初始时每个元素自成一个集合：

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

这表示一开始有 10 棵只有根结点的树。

合并后的示意

如果经过若干次合并，得到三个集合：

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

可以表示为：

S1:        0          S2:      1          S3:      2
         / | \               /   \               /   \
        6  7  8             4     9             3     5

对应的双亲数组可以写成：

下标:  0   1   2   3   4   5   6   7   8   9
S[i]: -4  -3  -3   2   1   2   0   0   0   1

其中：

S[0] = -4 表示 0 是根，且集合 S1 中有 4 个元素。
S[1] = -3 表示 1 是根，且集合 S2 中有 3 个元素。
S[2] = -3 表示 2 是根，且集合 S3 中有 3 个元素。

3. 基本实现

结构定义

#define SIZE 100
int UFSets[SIZE];

3.1 初始化

void Initial(int S[]) {
    for (int i = 0; i < SIZE; i++) {
        S[i] = -1;
    }
}

初始化后，每个元素都是一棵只有根结点的树。

3.2 查找 Find

Find(S, x) 的目标是找到元素 x 所在树的根。

int Find(int S[], int x) {
    while (S[x] >= 0) {
        x = S[x];
    }
    return x;
}

思路很直接：不断沿着父结点往上跳，直到遇到根结点。

3.3 合并 Union

如果已经知道两个元素所在集合的根分别是 Root1 和 Root2，就可以把一个根接到另一个根下面。

void Union(int S[], int Root1, int Root2) {
    if (Root1 == Root2) {
        return;
    }
    S[Root2] = Root1;
}

例如把 S2 合并到 S1，可以理解成“让根 1 指向根 0”：

对应数组变为：

下标:  0   1   2   3   4   5   6   7   8   9
S[i]: -7   0  -3   2   1   2   0   0   0   1

4. 为什么要优化

朴素并查集虽然简单，但如果总是随意合并，树可能会越来越高。

极端情况下会退化成一条链：

0 <- 1 <- 2 <- 3 <- 4 <- 5

这时一次 Find 最坏需要沿链走到底，时间复杂度会退化到 O(n)。

因此并查集通常会做两类优化：

按集合大小合并
路径压缩

5. 按集合大小合并

思路是：把小树挂到大树下面，这样树高增长更慢。

因为根结点保存的是负数规模，所以绝对值越大，集合越大。

void Union(int S[], int Root1, int Root2) {
    if (Root1 == Root2) {
        return;
    }

    if (S[Root2] > S[Root1]) {
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    } else {
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
}

这里判断 S[Root2] > S[Root1] 的原因是：

例如 -3 > -5，说明 Root2 对应的集合更小。
所以应该把 Root2 挂到 Root1 下面。

采用这种策略后，树的深度可以控制得比较好；教材里常写成深度不超过 floor(log2 n) + 1。

6. 路径压缩

按大小合并已经能减少树高，但随着合并次数增多，树仍可能逐渐变深。进一步优化的方法是：在查找根的同时，把沿途结点直接挂到根上。

int Find(int S[], int x) {
    int root = x;

    while (S[root] >= 0) {
        root = S[root];
    }

    while (x != root) {
        int t = S[x];
        S[x] = root;
        x = t;
    }

    return root;
}

路径压缩示意

压缩前：

0
|
1
|
3
|
5

如果执行 Find(S, 5)，找到根结点 0 后，会把路径上的结点都直接连到根：

压缩后：

    0
  / | \
 1  3  5

这样下一次再查这些结点时，就会快很多。

7. 时间复杂度

不带优化时：

Find：O(d)，其中 d 是树的深度
Union：O(1)，前提是已经拿到了两个根

带按规模合并后：

树高明显降低
Find 的最坏情况比朴素写法更好

再叠加路径压缩后：

单次操作可以认为接近 O(1)
更严格地说，均摊复杂度是 O(alpha(n))
这里的 alpha(n) 是反阿克曼函数，增长极慢，在实际题目里几乎可以看成常数

8. 常见使用模板

写题时最常见的流程是：

void Merge(int S[], int a, int b) {
    int ra = Find(S, a);
    int rb = Find(S, b);
    if (ra != rb) {
        Union(S, ra, rb);
    }
}

判断两个元素是否连通：

int IsSameSet(int S[], int a, int b) {
    return Find(S, a) == Find(S, b);
}

9. 适合记住的要点

并查集解决的是“动态连通性”问题。
根结点代表一个集合。
Find 用来找根，Union 用来合并集合。
双亲数组里，非根存父结点，根存负数信息。
优化的关键是“小树并入大树”和“路径压缩”。

10. 可继续补充的题目方向

无向图连通块统计
岛屿问题
冗余边判断
最小生成树 Kruskal
账户合并、字符串分组等映射类问题