并查集
01 / 一句话本质
把N个元素维护成若干不相交的连通分量; 把两个分量合并为一个的代价接近常数。它是一片森林,根就是该分量的代表, 而每次find都会把它走过的那条路压扁。
题目用并查集统计连通分量节点数6边数5
初始:6 个节点,各自成为一个分量。依次处理每条边 — 每次 union 把两棵树合并。
步
0 / 16
边
—
动作
初始化
分量数
6
0 / 16
02 / 模式骨架
# 两个数组 + 两个操作parent[i] ← i # 每个元素一开始都是自己的根size[i] ← 1 def find(x):while parent[x] ≠ x:parent[x] ← parent[parent[x]] # 路径压缩x ← parent[x]return x def union(a, b):ra, rb ← find(a), find(b)if ra == rb: return Falseif size[ra] < size[rb]: ra, rb ← rb, raparent[rb] ← ra # 把较小的挂到较大的下面size[ra] += size[rb]return True
03 / 什么时候用这个模式
"连通分量"
需要统计或判断一组元素是否属于同一个组。等价关系:自反、对称、传递。 如果你想从每个节点都跑一次 BFS/DFS,那就该想到并查集了。
"合并两个组"
问题不断增量地把集群合并 — 朋友变成朋友的朋友、边一条一条加进来、共享邮箱的账号。合并的顺序并不重要,只有成员关系重要。
"无向图判环"
边一条一条加入;若一条边连接的两端已经属于同一连通分量,这条边就形成了环。 Kruskal 求最小生成树以及 LC 684 都用到这个。
"离线查询"
当查询可以批量处理(非在线)时,并查集能以接近常数的均摊代价回答 "经过这 k 次操作后,x 和 y 是否连通?"。
04 / 常见坑
i.
跳过两项优化。
没有路径压缩,或没有按大小/按秩合并,并查集在最坏情况下(左偏链)会退化到每次
O(N)。 只用其中之一能拿到 O(log N);两者都用才能拿到 α(N)。请始终同时使用两者 — 代码量都不到十行。ii.
比较前忘了 find。
判断"a 与 b 是否连通"必须比较
find(a) == find(b),而不是 parent[a] == parent[b]。后者只看直接父亲 — 只有在全树压平后才正确。iii.
遍历时修改。
路径压缩会在
find 中改写 parent 数组。 若你一边遍历 parent 一边对每个项调用 find, 就会看到不一致的中间状态。要么先做快照,要么只在确实需要最新的根时才调 find。05 / 去 LeetCode 上练习
家族中的四道题。第一道是经典的"省份数量"入门;接下来两道在其上增加结构(判环、带权边); 第四道把节点键改成字符串 — 在同一套并查集核心外加一层哈希映射。