一句话总结
并查集（Disjoint Set Union, DSU）维护一群元素的分组关系，只支持两个操作：union 合并两个集合 与 find 查询某元素属于哪个集合。它用一棵"代表元为根"的森林表示分组，靠路径压缩和按秩合并两个优化把单次操作压到近乎 O(1)——准确说是反阿克曼函数 α(n)，实际中不超过 5。
🌲
森林表示集合
每个集合是一棵树，树根的编号就是该集合的"代表"。
🔍
find(x)
沿 parent 指针一路向上找根，判断同属一个集合就看根是否相同。
🤝
union(x, y)
把 x 的根挂到 y 的根下面（或反之），两棵树合为一棵。
⚡
两个优化
路径压缩（find 时拉直）+ 按秩/大小合并，缺一不可。
一、核心结构与操作
1.1 森林示意
1.2 基础实现
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # parent[i] = i 表示 i 是根
self.rank = [0] * n # 树的"秩"（近似高度）
self.count = 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):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # 本来就同组（可用于判环）
# 按秩合并：矮树挂到高树下，避免树长高
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
self.count -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
二、两个关键优化
2.1 路径压缩（Path Compression）
2.2 按秩 / 按大小合并
💡 思路：永远把小树挂到大树下面（或矮树挂到高树下）。这样树的高度增长最慢。
按秩（rank）：rank 近似树高，只有两树 rank 相等时合并后 rank 才 +1。
按大小（size）：记录每个集合的元素个数，永远小的挂大的，同样能保证树高 O(log n)。
按秩（rank）：rank 近似树高，只有两树 rank 相等时合并后 rank 才 +1。
按大小（size）：记录每个集合的元素个数，永远小的挂大的，同样能保证树高 O(log n)。
⚠️ 两个优化缺一不可：只用路径压缩，最坏仍是 O(log n) 级别；只用按秩合并，树高 O(log n)；两者同时使用才达到 α(n) 的摊还近乎常数。面试手写时两个都写上。
三、典型应用
3.1 判环（无向图）
遍历每条边 (u, v)：如果 u、v 已经连通，说明这条边会形成环；否则 union 它们。
def has_cycle(n, edges):
uf = UnionFind(n)
for u, v in edges:
if uf.connected(u, v): # 两端已同组 → 再连就是环
return True
uf.union(u, v)
return False
3.2 连通分量计数（LeetCode 547 省份数量 / 200 岛屿）
def findCircleNum(isConnected):
n = len(isConnected)
uf = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
uf.union(i, j)
return uf.count # 剩下的集合数 = 省份数
3.3 Kruskal 最小生成树
把所有边按权重从小到大排序，依次尝试加入：若两端不连通就 union 并累计权重，否则跳过（会成环）。
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # 按权重升序
uf = UnionFind(n)
total, used = 0, 0
for u, v, w in edges:
if uf.union(u, v): # 返回 True 表示成功合并（不成环）
total += w
used += 1
if used == n - 1: # 生成树只需 n-1 条边
break
return total
3.4 其他常见场景
| 题目 / 场景 | 并查集扮演的角色 |
|---|---|
| 684 冗余连接 | 找那条会成环的边 |
| 990 等式方程的可满足性 | 等号建连通，不等号检查是否矛盾 |
| 128 最长连续序列 | 相邻数 union，统计最大集合大小 |
| 721 账户合并 | 邮箱与账户 ID 建映射后 union |
| 399 除法求值 | 带权并查集（维护到根的比例） |
| 社交网络好友关系 | 判断两人是否在同一圈子 |
四、复杂度与对比
| 实现方式 | find / union 复杂度 | 说明 |
|---|---|---|
| 朴素（不优化） | O(n) 最坏 | 树可能退化成链表 |
| 仅路径压缩 | O(log n) 摊还 | 好很多但非最优 |
| 仅按秩合并 | O(log n) | 树高有界 |
| 压缩 + 按秩 | O(α(n)) | α 是反阿克曼函数，n 为宇宙原子数时 α ≤ 5，实际视为 O(1) |
并查集 vs DFS/BFS：如果关系是静态的一次性查询（边全部给定后问连通性），两者都行。但如果边是动态逐步加入的（每加一条边就问"现在是否成环/有几个连通块"），并查集远优于每次重新 DFS——后者是 O(n) 每次，前者近乎 O(1)。
一句话记住：凡是题目里出现"连通""是否属于同一组""动态加边判断是否成环""合并集合"这类词，第一反应就该考虑并查集。