并查集 size 的优化：让算法更高效的关键一步
在解决“连通性”问题时，并查集（Union-Find）是一个非常实用的数据结构。它能快速判断两个元素是否属于同一个集合，也能高效地合并两个集合。但如果你只用最基础的并查集实现，随着数据规模增大，性能会急剧下降。
这时候，并查集 size 的优化就显得尤为重要。它不仅能显著提升查询和合并的效率，还能帮助我们更好地理解算法背后的逻辑。本文将带你一步步掌握这一核心优化技巧，从零开始构建一个高效的并查集。
什么是并查集？
并查集，顾名思义，就是“合并”和“查找”集合。它的核心功能有两个：
union(x, y)：将元素 x 和 y 所在的集合合并。find(x)：找出元素 x 所在集合的代表元（根节点）。
想象一下，你有一堆人，他们之间有些是朋友关系。你想快速知道两个人是不是在一个朋友圈里，或者把两个朋友圈合并成一个。这就是并查集要解决的问题。
在最原始的实现中，我们用一个数组 parent 来记录每个元素的父节点，初始时每个元素的父节点都是自己。
基础实现与性能瓶颈
我们先来看一个基础版本的并查集实现：
class UnionFind:
def __init__(self, n):
# 初始化每个节点的父节点为自己
self.parent = [i for i in range(n)]
def find(self, x):
# 递归查找根节点
if self.parent[x] != x:
return self.find(self.parent[x])
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
这个版本逻辑清晰，但问题来了：如果树的结构越来越“偏斜”，比如 1 指向 2，2 指向 3，……，n-1 指向 n，那么 find 操作的时间复杂度会退化到 O(n)。
这就像一条长链，每次查找都要走完所有节点。这显然无法满足大规模数据的需求。
引入 size 优化：用“大小”来指导合并
为了解决这个问题，我们引入一个新变量：size。它记录每个集合（以根节点为标识）所包含的元素个数。
当我们合并两个集合时，不再随意指定父节点，而是把小集合合并到大集合中。这个策略叫“按 size 合并”或“按秩合并”（虽然秩是另一个概念，但这里可以类比理解）。
这样做有什么好处？可以有效控制树的高度，避免出现极端偏斜的结构。
创建数组与初始化
class UnionFind:
def __init__(self, n):
# parent[i] 表示 i 的父节点
self.parent = [i for i in range(n)]
# size[i] 表示以 i 为根的集合的大小
self.size = [1] * n
这里我们多了一个 size 数组，初始时每个元素单独成一个集合，所以大小都是 1。
合并操作的优化逻辑
def union(self, x, y):
# 先找到两个元素的根节点
root_x = self.find(x)
root_y = self.find(y)
# 如果已经在同一个集合，无需合并
if root_x == root_y:
return
# 按 size 合并：把小树接到大树上
if self.size[root_x] < self.size[root_y]:
# root_x 的集合更小，把它挂到 root_y 下
self.parent[root_x] = root_y
self.size[root_y] += self.size[root_x] # 更新大树的 size
else:
# root_y 更小或相等，挂到 root_x
self.parent[root_y] = root_x
self.size[root_x] += self.size[root_y]
这段代码的核心思想是：永远把小集合合并到大集合中。这就像把一个小团队并入大公司，而不是反过来，这样能减少“管理层级”，让查找更高效。
查找操作的路径压缩优化（协同优化）
虽然 size 优化已经很好了，但如果我们再配合“路径压缩”，性能会更上一层楼。
路径压缩的原理是：在 find 的过程中，把所有经过的节点都直接指向根节点。
def find(self, x):
if self.parent[x] != x:
# 递归查找根节点，并把路径上所有节点都指向根
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
这个优化非常关键。它让后续的 find 操作变成 O(1) 的常数时间。
📌 小贴士：路径压缩和 size 优化同时使用时，时间复杂度接近 O(α(n))，其中 α 是反阿克曼函数，增长极其缓慢，几乎可以看作常数。
实际案例：岛屿数量问题
我们用一个经典问题来验证 size 优化的实际效果。
题目：给你一个 m × n 的二维网格，网格中 '1' 表示陆地，'0' 表示水。求岛屿的数量（上下左右相连的陆地算一个岛屿）。
使用并查集，我们可以把相邻的 '1' 节点合并，最后统计根节点的数量。
代码实现（带 size 优化）
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
# 按 size 合并：小树挂到大树上
if self.size[root_x] < self.size[root_y]:
self.parent[root_x] = root_y
self.size[root_y] += self.size[root_x]
else:
self.parent[root_y] = root_x
self.size[root_x] += self.size[root_y]
def numIslands(grid):
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
uf = UnionFind(m * n)
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 四个方向
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
# 将当前格子映射为一维索引
idx = i * n + j
# 检查四个方向的邻居
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == '1':
nidx = ni * n + nj
uf.union(idx, nidx)
# 统计根节点的数量，即岛屿数量
roots = set()
for i in range(m * n):
if grid[i // n][i % n] == '1':
roots.add(uf.find(i))
return len(roots)
在这个例子中，并查集 size 的优化让合并操作更加稳定，避免了树的深度失控，从而保证了整体算法的高效性。
性能对比：优化前 vs 优化后
我们来对比一下不同实现的性能表现：
| 优化方式 | 查找时间复杂度 | 合并时间复杂度 | 是否推荐 |
|---|---|---|---|
| 无优化（随意合并） | O(n) | O(1) | ❌ 不推荐 |
| 仅 size 优化 | O(log n) | O(1) | ✅ 推荐 |
| size + 路径压缩 | O(α(n)) | O(α(n)) | ✅✅ 强烈推荐 |
可以看到，并查集 size 的优化是性能提升的关键一步。即使不加路径压缩，仅靠 size 优化，也能将最坏情况从 O(n) 降到 O(log n)。
常见误区与调试建议
- 不要忘记更新 size：合并时，必须更新新根节点的 size，否则优化失效。
- 路径压缩要递归使用：
find中的self.parent[x] = self.find(...)是关键。 - 索引映射要正确：二维数组转一维时，
i * n + j必须准确。 - 边界检查不能漏：合并前要判断是否已在同一集合。
调试时，可以用打印 size 数组和 parent 数组的方式，观察合并过程是否合理。
总结：为什么 size 优化如此重要？
并查集虽然结构简单，但它的性能高度依赖于合并策略。并查集 size 的优化不仅仅是一个技巧，更是一种思维方式——用数据本身的信息来指导算法行为。
当你面对大规模连通性问题时，不要只满足于“能跑通”，更要追求“跑得快”。size 优化就是让你从“能用”走向“高效”的关键一步。
无论是处理社交网络、图像分割，还是图论中的连通分量问题，掌握这一优化，都能让你的代码更具竞争力。
记住：算法的优雅，不仅在于逻辑正确，更在于效率与可扩展性。从今天起，让每一次合并，都变得更聪明。