并查集基础：从零理解数据结构中的“集合管家”
在算法世界里，有些数据结构像“幕后英雄”，不张扬却极为关键。并查集（Union-Find）就是其中之一。它虽然不像二叉树或哈希表那样频繁出现在面试题的“热搜榜”上，但一旦遇到“连通性问题”，它往往能用极简的代码给出优雅解法。今天，我们就来聊一聊并查集基础，带你从零开始掌握这个小而美的工具。
并查集的核心能力是：快速判断两个元素是否属于同一个集合，以及合并两个集合。它特别适合处理动态连通性问题——比如社交网络中判断两个人是否“认识”，或者地图上判断两个城市是否通过道路连通。
如果你正在准备算法面试，或者想提升代码设计的思维，掌握并查集基础是必经之路。接下来，我们一步步拆解它的原理与实现。
理解并查集的核心思想
想象你有若干个独立的盒子，每个盒子里放着一些人。一开始，每个人都是独立的，属于自己的“小圈子”。当你发现两个人是朋友时，就把他们所在的盒子合并成一个更大的盒子。这个过程，就是“合并集合”。
并查集就是模拟这种“合并与查询”的操作。它支持两个核心操作：
union(x, y)：把 x 和 y 所在的集合合并find(x)：找出 x 所在集合的代表元（根节点）
举个生活化的例子：你有一堆散落的乐高积木，每个积木是一个独立的块。当你把两个积木拼在一起，它们就属于同一个“组合体”。并查集就是记录这些组合关系的“拼接图谱”。
创建数组与初始化
并查集最基础的实现方式是用一个数组 parent 来表示每个元素的父节点。初始时，每个元素的父节点是自己，表示它们各自独立成一个集合。
def init_union_find(n):
parent = [i for i in range(n)] # 每个元素的父节点初始化为自己
return parent
这里的关键是：parent[i] == i 表示 i 是所在集合的根节点。当两个元素的根节点相同时，说明它们属于同一个集合。
注释说明：
parent数组的索引表示元素编号，值表示它的父节点编号。- 初始时，每个元素的父节点是自己，表示“独立集合”。
- 后续通过
union操作改变父节点关系，最终形成树形结构。
实现 find 操作：找根节点
find(x) 的目标是找到 x 所在集合的根节点。由于并查集是用树形结构表示集合的，我们需要沿着父节点一路向上找，直到找到根（即 parent[x] == x）。
def find(parent, x):
# 递归方式：一直找父节点，直到根节点
if parent[x] != x:
parent[x] = find(parent, parent[x]) # 路径压缩优化
return parent[x]
注释说明：
- 如果
parent[x] == x，说明 x 是根节点，直接返回。- 否则，递归查找父节点的根，并将
parent[x]更新为根节点，这叫“路径压缩”——大幅减少后续查找时间。- 路径压缩是并查集性能优化的关键技巧之一。
举个例子：
假设 parent = [0, 1, 2, 3, 4]，调用 find(3) 会返回 3。
如果之后执行 union(3, 4)，把 4 的父节点设为 3，再调用 find(4)，结果会是 3。
实现 union 操作：合并两个集合
union(x, y) 的逻辑是：先找到 x 和 y 的根节点，如果不同，就把其中一个根节点指向另一个，从而合并两个集合。
def union(parent, x, y):
root_x = find(parent, x) # 找到 x 的根
root_y = find(parent, y) # 找到 y 的根
if root_x == root_y:
return # 已经在同一集合，无需合并
# 将 root_x 的父节点设为 root_y，实现合并
parent[root_x] = root_y
注释说明：
- 先用
find找到两个元素的根节点。- 如果根相同，说明已在同一集合，直接返回。
- 否则，将一个根的父节点设为另一个根，完成合并。
- 注意：这里我们选择把
root_x指向root_y，但也可以反过来，不影响逻辑。
优化策略：路径压缩与按秩合并
虽然上面的实现已经能工作，但性能可能在极端情况下下降。为此，我们引入两个优化：
路径压缩（Path Compression）
在 find 操作中，将所有经过的节点直接指向根节点，让后续查找更快。
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x]) # 递归压缩路径
return parent[x]
效果：原本的树形结构会被“拉直”，所有节点都直接连到根。
按秩合并（Union by Rank）
用一个额外数组 rank 记录每个根节点的“深度”（或高度）。合并时，总是把矮树接到高树上，避免树变得过深。
def init_union_find_with_rank(n):
parent = [i for i in range(n)]
rank = [0] * n # 每个节点的秩初始化为 0
return parent, rank
def union(parent, rank, x, y):
root_x = find(parent, x)
root_y = find(parent, y)
if root_x == root_y:
return
# 按秩合并：秩小的树接到秩大的树上
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1 # 秩相等时，新根的秩加 1
注释说明：
rank不是实际高度，而是估计值，用于优化合并顺序。- 保证树尽量“扁平”，减少
find操作的时间。
实际应用：岛屿数量问题（LeetCode 200）
让我们用并查集解决一个经典问题：岛屿数量。
题目：给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。一个岛屿由相邻的陆地连接形成。
我们可以用并查集维护每个陆地单元的连通关系。
def num_islands(grid):
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
parent = [i for i in range(rows * cols)]
rank = [0] * (rows * cols)
# 方向数组：上下左右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
root_x = find(x)
root_y = find(y)
if root_x == root_y:
return
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
# 遍历每个格子
for i in range(rows):
for j in range(cols):
if grid[i][j] == '0':
continue # 水，跳过
# 将当前格子映射为一维索引
idx = i * cols + j
# 检查四个方向
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1':
nidx = ni * cols + nj
union(idx, nidx)
# 统计根节点的数量（即岛屿数量）
roots = set()
for i in range(rows * cols):
if grid[i // cols][i % cols] == '1':
roots.add(find(i))
return len(roots)
注释说明：
- 将二维网格转换为一维数组索引，方便并查集操作。
- 遍历每个陆地格子，尝试与相邻的陆地合并。
- 最后统计所有“根节点”数量，就是岛屿数。
- 时间复杂度接近 O(MN × α(MN))，α 是阿克曼函数的反函数，几乎恒为常数。
并查集基础的适用场景总结
并查集基础虽然简单，但威力巨大。它最适合以下场景：
- 动态连通性判断（如社交网络、网络拓扑）
- 图的连通分量统计（如岛屿数量、冗余连接）
- 构造最小生成树（Kruskal 算法中使用）
- 实现等价类划分（如编译器中的符号解析）
它的优势在于：代码简洁、逻辑清晰、性能优秀。在多数情况下，经过优化的并查集，单次操作的时间复杂度接近 O(1)，远超普通 DFS/BFS。
小结：掌握并查集基础，提升算法思维
今天我们从并查集的核心思想出发，一步步实现了初始化、查找、合并操作，并引入了路径压缩与按秩合并两大优化技巧。通过岛屿数量这一实际案例，我们验证了并查集在真实问题中的强大表现。
并查集基础不是“高阶算法”，但它能让你在面对连通性问题时，不再手忙脚乱。它教会我们如何用简单的数据结构，解决复杂的逻辑问题。
算法不是堆砌代码，而是理解本质。当你下次遇到“是否连通”“合并集合”这类问题时，不妨先想想：能不能用并查集？
别小看这个小小的数据结构。它可能正是你算法能力跃迁的关键一步。