在这一节中，我们将深入探讨一种在计算机科学中非常实用且优雅的数据结构——并查集（Disjoint Set Union，简称 DSU）。如果你在日常开发或算法面试中遇到过“动态连通性”、“最小生成树”或“图论中的集合合并”等问题，那么你一定会惊叹于它的高效与简洁。它不像二叉搜索树或红黑树那样复杂，但却能以近乎常数的时间复杂度解决看似棘手的集合管理问题。让我们一起踏上探索并查集的旅程，揭开它神秘的面纱。
1. 什么是并查集？
并查集，顾名思义，是一种专门用于处理不相交集合（Disjoint Sets）的合并与查询问题的树型数据结构。为了让你更直观地理解，我们可以想象这样一个场景：在一个巨大的社交网络中，有无数个用户。起初，每个人都是独立的，互不认识。随着时间推移，人们开始建立朋友关系（我们需要将这两个人所在的社交圈合并）。最后，系统需要快速判断任意两个人是否属于同一个朋友圈（直接或间接的朋友关系）。
这就是并查集要解决的核心问题：
- 合并：将两个不同的集合连接在一起。
- 查询：快速判断两个元素是否属于同一个集合。
在并查集中，我们并不关心集合的具体形状，也不关心某个具体元素在集合中的位置，我们只关心两个元素是否连通。为了实现这一点，我们为每个集合选出一个“代表”，通常称为根节点。
2. 核心操作详解
并查集主要支持两个核心操作，理解它们的工作原理是掌握这一数据结构的关键。
#### Find（查找）：寻找集合的代表
查找操作的目标是找到元素所在的集合的“根节点”。在这个树型结构中，如果一个节点的父节点是它自己，那么它就是根节点。它是这个集合的最高领导者。我们通过不断追溯父节点，直到找到根节点为止。
#### Union（合并）：连接两个集合
合并操作的本质是将两棵独立的树连接成一棵树。通常的做法是：找到两个元素各自的根节点，如果根节点不同，就将其中一个根节点指向另一个根节点，从而完成集合的合并。
3. 基础实现与代码解析
为了保持代码的通用性和清晰度，下面的代码示例我们将保留英文关键字和注释，并结合中文进行详细讲解。
#### 3.1 最基础的实现
首先，让我们从最简单的版本开始。虽然这个版本在极端情况下效率不高，但它是理解后续优化的基础。
在这个实现中，我们维护一个 INLINECODE5797836f 数组。INLINECODEe80a3b5c 存储的是元素 i 的父节点。
class DSU:
def __init__(self, size):
# 初始化：每个元素的父节点都是自己
# 这意味着最初每个元素都是一个独立的集合
self.parent = list(range(size))
def find(self, i):
# 查找操作：递归地寻找根节点
# 根节点的定义是：父节点指向自己
if self.parent[i] != i:
return self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
# 合并操作：找到两个元素各自的根节点
root_i = self.find(i)
root_j = self.find(j)
# 如果根节点不同，说明它们在不同的集合中
# 我们将 root_i 挂载到 root_j 上，或者反过来
if root_i != root_j:
self.parent[root_i] = root_j
代码工作原理：
- 初始化：当我们创建 INLINECODE3c221ed4 时，实际上建立了 5 棵只有根节点的树：INLINECODEa969c064。
- 查找：当你调用
find(4)时，如果它的父节点是它自己，直接返回 4。如果它的父节点是 2，而 2 的父节点是 0，0 的父节点是 0，那么递归调用会最终返回 0。 - 合并：当你调用 INLINECODEee9c19b2 时，程序会先找到 1 的根（假设是 1）和 2 的根（假设是 2）。然后执行 INLINECODEe318a549。这样，1 就成了 2 的子节点，集合 INLINECODE475fcf3f 和 INLINECODE5f2a766c 就连通了。
#### 3.2 第一次优化：路径压缩
你可能会发现上面的 find 操作有一个潜在的问题：如果树变得很高（比如一条链），每次查找都需要遍历很长的路径，效率就会退化。为了解决这个问题，我们引入了一个极其重要的优化技巧——路径压缩（Path Compression）。
它的核心思想是：既然我们费尽千辛万苦找到了根节点，为什么不顺便把沿途所有节点的父节点都直接指向根节点呢？ 这样下次再查询这些节点时，速度就会飞快。
def find(self, i):
if self.parent[i] != i:
# 路径压缩的关键代码：
# 在递归返回的过程中，将 i 的父节点直接设为根节点
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
实用见解：
这个简单的改动极大地提升了性能。当我们第二次查找同一个节点时，时间复杂度直接变成了 O(1)。这是一种“懒加载”式的优化，只有在查询时才去调整树的结构。
4. 进阶优化：按秩合并
虽然路径压缩已经很强大了，但在频繁的合并操作中，如果我们总是盲目地将一棵树挂到另一棵树上，树仍然有可能变得很高。为了进一步控制树的高度，我们引入了按秩合并（Union by Rank）或按大小合并（Union by Size）。
这里的“秩”通常指树的高度估算或集合的大小。我们的策略是：将矮树（或小树）挂到高树（或大树）的根节点上。这样可以避免合并后树的高度增加。
class DSU:
def __init__(self, size):
self.parent = list(range(size))
# rank 数组用于记录树的高度或秩的估算值
# 初始化时，所有节点的高度为 0
self.rank = [0] * size
def find(self, i):
# 依然使用路径压缩
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)
if root_i != root_j:
# 按秩合并逻辑
# 比较 root_i 和 root_j 的秩
if self.rank[root_i] > self.rank[root_j]:
# i 的树更高，把 j 挂到 i 上
self.parent[root_j] = root_i
elif self.rank[root_i] < self.rank[root_j]:
# j 的树更高，把 i 挂到 j 上
self.parent[root_i] = root_j
else:
# 高度相同，随便挂，但记得增加挂载后的树的秩
self.parent[root_j] = root_i
self.rank[root_i] += 1
算法分析：
结合了路径压缩和按秩合并的并查集，其操作的平均时间复杂度非常低，可以近似看作是常数时间 O(α(n))，其中 α 是阿克曼函数的反函数。这是一个极其缓慢增长的函数，对于所有实际应用场景（例如 n 远小于地球的原子总数），α(n) 都小于 5。因此，我们在工程实践中可以自信地认为它的效率是 O(1)。
5. 实战应用：岛屿数量问题
理论讲完了，让我们来看看并查集在实际算法问题中是如何大显身手的。经典的“岛屿数量”问题是练习并查集的绝佳案例。
问题描述：
给定一个由 ‘1‘（陆地）和 ‘0‘（水）组成的二维网格，计算岛屿的数量。一个岛屿被水包围，并且通过水平或垂直方向上相邻的陆地连接而成。
解题思路：
- 遍历整个网格，把所有的陆地节点进行编号（0 到 n-1）。
- 初始化并查集，将每个陆地节点视为独立的集合。
- 再次遍历网格，对于每个陆地节点，检查它的右边和下边是否也是陆地。
- 如果是，就调用
union操作将这两个节点合并。 - 最后，统计
find(i) == i的节点数量，也就是根节点的数量，这就是岛屿的数量。
代码示例：
class DSU:
def __init__(self, size):
self.parent = list(range(size))
# 这里我们使用按大小合并，稍微改变一下策略
self.size = [1] * size
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)
if root_i != root_j:
# 将较小的树合并到较大的树下
if self.size[root_i] < self.size[root_j]:
root_i, root_j = root_j, root_i
self.parent[root_j] = root_i
self.size[root_i] += self.size[root_j]
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
# 辅助函数：将二维坐标 (r, c) 转换为一维索引 index
def get_index(r, c):
return r * cols + c
# 第一步：统计陆地数量并初始化 DSU
land_count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
land_count += 1
# 初始化 DSU 大小为网格总面积
dsu = DSU(rows * cols)
# 这一步用来标记哪些位置是水，初始化时我们可以让所有水的根节点指向一个特殊的虚拟节点
# 但为了简单，我们在逻辑里判断即可
# 第二步：遍历并合并
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
# 检查下方邻居
if r + 1 < rows and grid[r+1][c] == "1":
dsu.union(get_index(r, c), get_index(r+1, c))
# 检查右方邻居
if c + 1 < cols and grid[r][c+1] == "1":
dsu.union(get_index(r, c), get_index(r, c+1))
# 第三步：统计根节点数量
roots = set()
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
roots.add(dsu.find(get_index(r, c)))
return len(roots)
6. 常见错误与最佳实践
在使用并查集时，你可能会遇到一些“坑”。作为经验丰富的开发者，我想提醒你注意以下几点：
- 数组越界：这是最常见的错误。在 INLINECODEb4d4fd59 或 INLINECODE440641fd 之前，务必确认传入的元素索引 INLINECODE2e392442 和 INLINECODE6b3837b3 是合法的（在 0 到 size-1 之间）。
- 忽略路径压缩：虽然手写简单的 INLINECODE56334f9c 函数很容易，但如果不加路径压缩，在处理大规模数据（如 10^5 级别）时，程序很可能会超时（TLE）。记得加上那句 INLINECODE7cfbc7db。
- 混淆输入值与数组索引：如果输入数据是 INLINECODEabf04189 到 INLINECODE475530df，而你的数组是 INLINECODE3254f26a 到 INLINECODE4521b8bd，记得在访问 INLINECODE0efd3926 前进行转换（例如 INLINECODEc9717bf1）。
- 按秩 vs 按大小：通常情况下，按大小合并有时比按高度（Rank）合并更直观，因为
size数组在统计集合大小时也很有用。你可以根据实际需求选择，两者在防止树退化上的效果是一致的。
7. 更多应用场景
除了岛屿数量，并查集还在以下领域有着广泛的应用：
- Kruskal 最小生成树算法：这是图论中的经典算法。我们需要对所有边按权重排序，然后依次尝试加入图中。为了避免形成环，我们使用并查集：如果要加入的边的两个端点已经在同一个集合里（连通），就跳过；否则加入并合并集合。
- 动态连通性：在社交网络或网络传输中，实时判断两点是否连通。
- 等式方程的可满足性：给定一组等式（如 a==b）和不等式（如 a!=c），判断是否有矛盾。我们可以用并查集维护相等关系。
- 离线查询处理：有时候我们并不是实时处理请求，而是收集一批请求后统一处理。并查集非常适合这种“倒序处理”或“离线合并”的场景。
总结
通过这篇文章，我们从零开始构建了一个并查集，了解了它的核心思想，掌握了路径压缩和按秩合并两大优化法宝，并亲手解决了岛屿数量这一实际问题。你可以看到，并查集虽然代码量不大，但其设计的思想却非常精妙。
在接下来的学习和练习中，建议你尝试手动实现一遍 Kruskal 算法，或者去解决一些关于“省份数量”、“冗余连接”的问题，巩固你对这一数据结构的理解。掌握它，你的算法武器库中又多了一把锋利的剑！