并查集（Union-Find）：高效处理动态连通性问题

并查集（Union-Find，也叫 Disjoint Set Union，简称 DSU）是一种用于处理动态连通性问题的数据结构。它能高效地判断两个元素是否属于同一集合，以及合并两个集合。

为什么面试官喜欢考并查集

FAANG 面试中，并查集是一个非常热门的考点，因为它能测试：

数据结构设计能力：如何用数组表示树形结构
优化思维：路径压缩和按秩合并的优化技巧
算法应用能力：识别何时能用并查集解决问题
复杂度分析：理解均摊复杂度 $\alpha(n)$

常见应用：图的连通性、最小生成树 (Kruskal)、社交网络、等价类问题

核心概念：用软件架构的视角理解

对于有软件架构经验的你，可以把并查集想象成一个组织架构管理系统：

公司组织架构类比：

CEO (根节点)
├── CTO (中间节点)
│   ├── 开发经理
│   │   ├── 程序员 A
│   │   └── 程序员 B
│   └── 测试经理
│       └── 测试员 C
└── CFO
    └── 会计 D

Find(程序员A) = 找到 CEO（最高领导）
Union(公司A, 公司B) = 两家公司合并
IsConnected(A, B) = 两个人是否在同一家公司

核心操作：

Find(x)：找到 x 所属集合的代表元素（根节点）
Union(x, y)：合并 x 和 y 所在的两个集合
IsConnected(x, y)：判断 x 和 y 是否在同一集合

交互式可视化

观察并查集如何工作，包括 Union 和 Find 操作，以及路径压缩的效果：

并查集可视化

Step 0 of 16Connected Components: 6

Initialize 6 elements, each in its own set. parent[i] = i for all nodes.

Pending

Connected

Root

Current

Parent Array

0: 0

1: 1

2: 2

3: 3

4: 4

5: 5

Rank Array

0: 0

1: 0

2: 0

3: 0

4: 0

5: 0

Operations to Process

union(0, 1)

union(1, 2)

union(3, 4)

union(4, 5)

union(2, 4)

仔细观察：

初始状态：每个节点都是自己的根
Union 操作：将两个树合并
路径压缩：Find 时将路径上的节点直接指向根
按秩合并：较矮的树挂到较高的树下

数据结构设计

核心数据

parent[] 数组：parent[i] 表示节点 i 的父节点
rank[]   数组：rank[i] 表示以节点 i 为根的树的秩（近似高度）

初始化

初始状态（n=5）：

parent: [0, 1, 2, 3, 4]  ← 每个元素指向自己
rank:   [0, 0, 0, 0, 0]  ← 初始秩为 0

逻辑结构：
  0    1    2    3    4   ← 5 个独立的集合（森林）

两大核心优化

1. 路径压缩（Path Compression）

问题：如果树退化成链表，Find 操作变成 O(n)

解决：在 Find 时，将路径上所有节点直接指向根

Before 路径压缩：          After 路径压缩：
        0                        0
        |                     /|\ \
        1                    1 2 3 4
        |
        2
        |
        3
        |
        4

find(4) 过程：
4 → 3 → 2 → 1 → 0 (找到根)
然后将 4, 3, 2, 1 全部直接指向 0

2. 按秩合并（Union by Rank）

问题：随意合并可能导致树变得很高

解决：总是将较矮的树挂到较高的树下

Union(A, B)：

情况 1：rank[A] < rank[B]
    A 挂到 B 下面，rank 不变

情况 2：rank[A] > rank[B]
    B 挂到 A 下面，rank 不变

情况 3：rank[A] == rank[B]
    B 挂到 A 下面，rank[A]++

为什么有效？
保持树的高度尽可能小，从而保证 Find 操作高效

代码模板

关键点：

路径压缩用递归实现最简洁：parent[x] = find(parent[x])
按秩合并在 Union 中实现，比较两个根的 rank
count 变量可选，用于追踪连通分量数量

问题一：省份数量 (LC 547)

问题描述

给定一个 n x n 的邻接矩阵 isConnected，其中 isConnected[i][j] = 1 表示城市 i 和城市 j 直接相连。返回省份的数量（连通分量的数量）。

思路

这是并查集的经典应用：

遍历邻接矩阵
如果两个城市直接相连，执行 Union
最后返回连通分量的数量

示例：
isConnected = [[1,1,0],
               [1,1,0],
               [0,0,1]]

城市 0 和 1 相连 → Union(0, 1)
城市 2 独立

结果：2 个省份

代码实现

复杂度分析

时间复杂度： $O(n^2 \cdot \alpha(n)) \approx O(n^2)$ $O (n^{2} \cdot α (n)) \approx O (n^{2})$
- 需要遍历整个邻接矩阵
- 每次 Union/Find 操作近乎 O(1)
空间复杂度： $O(n)$ 用于并查集数组

问题二：冗余连接 (LC 684)

问题描述

树是一个连通且无环的图。给定一个有 n 个节点（编号从 1 到 n）的树，添加了一条额外的边。找出并返回这条多余的边。

思路

关键洞察：添加一条边时，如果两端点已经连通，那这条边就是冗余的

示例：edges = [[1,2], [1,3], [2,3]]

处理 [1,2]: 1 和 2 不连通 → Union(1, 2)
处理 [1,3]: 1 和 3 不连通 → Union(1, 3)
处理 [2,3]: 2 和 3 已连通 → 这就是冗余边！

冗余连接可视化

Step 0 of 10Connected Components: 4

Initialize 4 elements, each in its own set. parent[i] = i for all nodes.

Pending

Connected

Root

Current

Parent Array

0: 0

1: 1

2: 2

3: 3

Rank Array

0: 0

1: 0

2: 0

3: 0

Operations to Process

union(1, 2)

union(1, 3)

union(2, 3)

代码实现

复杂度分析

时间复杂度： $O(n \cdot \alpha(n)) \approx O(n)$
空间复杂度： $O(n)$

面试要点

按顺序处理边：题目保证返回最后出现的冗余边
节点编号从 1 开始：并查集大小需要 n+1
可能的追问：如果是有向图怎么办？(LC 685)

问题三：账户合并 (LC 721)

问题描述

给定一个账户列表，每个账户包含姓名和若干邮箱。如果两个账户有相同的邮箱，它们属于同一个人。合并所有账户。

思路

这是一个典型的等价类问题：

相同邮箱 = 相同人：遇到相同邮箱就 Union 两个账户
建立映射：邮箱 → 账户索引
收集结果：找到每个连通分量的所有邮箱

示例：
accounts = [
  ["John", "john@mail.com", "john00@mail.com"],  // 账户 0
  ["John", "johnnybravo@mail.com"],               // 账户 1
  ["John", "john@mail.com", "john_newyork@mail.com"], // 账户 2
  ["Mary", "mary@mail.com"]                       // 账户 3
]

账户 0 和 账户 2 都有 "john@mail.com" → Union(0, 2)

结果：
- John: john00@mail.com, john@mail.com, john_newyork@mail.com
- John: johnnybravo@mail.com
- Mary: mary@mail.com

代码实现

复杂度分析

设 N 为账户数，K 为每个账户平均邮箱数：

时间复杂度： $O(NK \cdot \alpha(N) + NK \cdot \log(NK))$ $O (N K \cdot α (N) + N K \cdot lo g (N K))$
- Union 操作： $O(NK \cdot \alpha(N))$
- 排序邮箱： $O(NK \cdot \log(NK))$
空间复杂度： $O(NK)$

问题四：最长连续序列 (LC 128)

问题描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列的长度。要求 O(n) 时间复杂度。

思路

把连续的数字想象成需要合并的集合：

遍历数组，对于每个数 num
检查 num-1 和 num+1 是否存在
如果存在，Union 它们
最后找最大的连通分量

示例：nums = [100, 4, 200, 1, 3, 2]

处理 100: 99 和 101 都不存在
处理 4: 3 不存在，5 不存在
处理 200: 199 和 201 都不存在
处理 1: 0 不存在，2 不存在
处理 3: 2 不存在（还没处理），4 存在 → Union(3, 4)
处理 2: 1 存在 → Union(2, 1)，3 存在 → Union(2, 3)

最终 {1, 2, 3, 4} 在同一集合，长度 = 4

代码实现

复杂度分析

时间复杂度： $O(n \cdot \alpha(n)) \approx O(n)$
空间复杂度： $O(n)$

注意：这道题用 HashSet 解法更简洁（只对序列起点计算长度），但并查集解法展示了它的通用性。

复杂度分析深度解析

时间复杂度

操作	无优化	仅路径压缩	仅按秩合并	两者都用
Find	O(n)	O(log n) 均摊	O(log n)	O(α(n))
Union	O(n)	O(log n) 均摊	O(log n)	O(α(n))

$\alpha(n)$ 是阿克曼函数的反函数，增长极其缓慢：

α(1) = 1
α(4) = 2
α(65536) = 3
α(2^65536) = 4

对于任何实际问题，α(n) ≤ 4
因此可以认为是 O(1)

空间复杂度

parent[] 数组：O(n)
rank[] 数组：O(n)
总空间：O(n)

边界情况与常见错误

1. 节点编号问题

// ❌ 错误：节点从 1 开始，但数组大小只有 n
UnionFind uf = new UnionFind(n);
uf.union(1, 2); // 可能越界！

// ✅ 正确：多分配一个空间
UnionFind uf = new UnionFind(n + 1);

2. 忘记检查是否已连通

// ❌ 错误：直接合并，无法判断是否形成环
uf.union(u, v);

// ✅ 正确：先检查
if (!uf.isConnected(u, v)) {
    uf.union(u, v);
}

3. 路径压缩的实现

// ❌ 错误：只压缩一层
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = parent[parent[x]]; // 只跳一层
    }
    return parent[x];
}

// ✅ 正确：完全压缩
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 递归压缩整条路径
    }
    return parent[x];
}

什么时候用并查集

✅ 适合使用

判断图的连通性
求连通分量数量
检测无向图中的环
动态连通性查询（边不断添加）
等价类合并问题

❌ 不适合使用

需要删除边（并查集不支持高效删除）
需要找最短路径
需要遍历整个连通分量
有向图的强连通分量

与其他算法的比较

场景	并查集	DFS/BFS
静态图连通性	✅ 更快	✅ 可以
动态添加边	✅ 最佳	❌ 需要重建
删除边	❌ 不支持	✅ 可以重建
找路径	❌ 只知道是否连通	✅ 可以记录路径
最短路径	❌	✅ BFS

面试技巧

如何向面试官解释

画图：画出树形结构，展示 Union 和 Find 过程
强调优化：主动提到路径压缩和按秩合并
分析复杂度：说明 α(n) 近乎 O(1)

常见追问

为什么用 rank 而不是 size？
- 两者都可以，rank 是树的高度上界
- 用 size（集合大小）也能保证 O(log n)
能否支持删除操作？
- 标准并查集不支持
- 可以用可持久化并查集或离线处理
如何优化空间？
- 如果只需要判断连通性，可以省略 rank 数组
- 但会影响最坏情况复杂度

练习题推荐

入门

中等

困难

总结

并查集 = 森林：用 parent 数组表示父子关系
两大优化缺一不可：路径压缩 + 按秩合并 → O(α(n))
适用场景：动态连通性、连通分量数量、检测环
面试关键：会写模板、知道应用场景、能分析复杂度

记住这个口诀：查找找根压路径，合并比秩矮挂高

掌握并查集后，你会发现很多图论问题都能用它高效解决！