并查集
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 / 常见坑
跳过两项优化。
没有路径压缩,或没有按大小/按秩合并,并查集在最坏情况下(左偏链)会退化到每次
O(N)。 只用其中之一能拿到 O(log N);两者都用才能拿到 α(N)。请始终同时使用两者 — 代码量都不到十行。比较前忘了 find。
判断"a 与 b 是否连通"必须比较
find(a) == find(b),而不是 parent[a] == parent[b]。后者只看直接父亲 — 只有在全树压平后才正确。遍历时修改。
路径压缩会在
find 中改写 parent 数组。 若你一边遍历 parent 一边对每个项调用 find, 就会看到不一致的中间状态。要么先做快照,要么只在确实需要最新的根时才调 find。05 / 去 LeetCode 上练习
中等20
01Longest Consecutive Sequence— LC 128→02Surrounded Regions— LC 130→03Number of Islands— LC 200→04Graph Valid Tree— LC 261→05Number of Connected Components in an Undirected Graph— LC 323→06Evaluate Division— LC 399→07Number of Provinces— LC 547→08Redundant Connection— LC 684→09Accounts Merge— LC 721→10Sentence Similarity II— LC 737→11Most Stones Removed with Same Row or Column— LC 947→12Satisfiability of Equality Equations— LC 990→13The Earliest Moment When Everyone Become Friends— LC 1101→14Connecting Cities With Minimum Cost— LC 1135→15Smallest String With Swaps— LC 1202→16Number of Operations to Make Network Connected— LC 1319→17Detect Cycles in 2D Grid— LC 1559→18Min Cost to Connect All Points— LC 1584→19Path With Minimum Effort— LC 1631→20Minimize Hamming Distance After Swap Operations— LC 1722→
困难11
01Number of Islands II— LC 305→02Redundant Connection II— LC 685→03Couples Holding Hands— LC 765→04Swim in Rising Water— LC 778→05Bricks Falling When Hit— LC 803→06Minimize Malware Spread— LC 924→07Largest Component Size by Common Factor— LC 952→08Optimize Water Distribution in a Village— LC 1168→09Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree— LC 1489→10Rank Transform of a Matrix— LC 1632→11Checking Existence of Edge Length Limited Paths— LC 1697→