处理「连通性」问题的利器：判断两个元素是否在同一集合、把两个集合合并。
典型题：朋友圈数量、岛屿数量、最小生成树 Kruskal。
模板
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x]) # 路径压缩
return self.p[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # 本来就连通
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra # 按规模合并
self.p[rb] = ra
self.size[ra] += self.size[rb]
return True
两个优化缺一不可
- 路径压缩：find 时把沿途节点直接挂到根上
- 按规模 / 秩合并：小树挂到大树下
只用其中一个，最坏情况仍可能退化；两个都用，复杂度接近 O(α(n))，
基本可以当成 O(1)。
什么时候想到它
题目出现「连通」「是否属于同一组」「合并集合」，
或者图的边是逐步加入的 —— 就是并查集。
楼主 · 2026-09-28 14:37 · 浏览 4
