01先从一个问题出发
朋友圈不断合并时,快速回答两个人是否已经在同一个圈子。
4 个节点,依次加入 (0,1)、(2,3)、(1,2)、(0,3)。大小相同则保留本次第一个根。
只问属于哪一组,不必每次找路线
图不断加入边,反复询问两点是否连通。每次 BFS 都能回答,却会重复搜索。并查集给每个连通组选择一个代表根;两个节点沿父指针找到同一根,就属于同一组。它记录分组,不负责还原图中的实际路径。
初始 n 个节点各自成组,parent[i]=i,size[i]=1,分量数为 n。加入边 (a,b) 时先求 find(a)、find(b)。如果根相同,已经连通,分量数不变;不同才把两组接起来。
两种压低树高的办法
按大小合并时,把较小集合的根接到较大集合的根上。必须修改根的父指针,而不是随便把 b 接到 a;后者可能只移动某一子树,破坏整组关系。只有根的 size 被用来代表集合大小。
路径压缩让查询经过的节点更接近根。本课采用路径减半:沿途把 parent[x] 改成 parent[parent[x]],然后继续走。祖父和当前节点原本就在同一组,所以改捷径不会改变组成员。父指针不是原图边,不要求这条捷径在原图中真实存在。
02最直接的办法,为什么慢?
每次询问连通性,都重新进行 BFS。
图不断加边、询问很多时,重复搜索整张图成本很高。
03一步步,推导出优化思路
用共同的根代表一个集合
每个集合选一个根作为代表,父指针连接到根。
查询时缩短父指针路径
find 走父指针,路径压缩把中途节点直接拉近根。
把小集合的根接到大集合
union 按大小把小树接到大树,减少未来查询深度。
两个节点连通,当且仅当 find 得到相同的根。
拿一个小输入,逐步手算
4 个节点,依次加入 (0,1)、(2,3)、(1,2)、(0,3)。大小相同则保留本次第一个根。
| 边 | 两端根 | parent[0..3] | 分量数 |
|---|---|---|---|
| 初始 | 各自为根 | [0,1,2,3] | 4 |
| (0,1) | 0 / 1 | [0,0,2,3] | 3 |
| (2,3) | 2 / 3 | [0,0,2,2] | 2 |
| (1,2) | 0 / 2 | [0,0,0,2] | 1 |
| (0,3) | 0 / 0 | [0,0,0,0] | 仍为 1;find 缩短了 3 的路径 |
合并完成不要求每个节点立刻直接指向根。第三步 parent[3]=2 仍合法,因为沿 3→2→0 能找到同一个代表。
分组与图的连通性同步变化
- 初始没有边,每个节点单独连通,与独立集合一致。
- 加入连接两个不同分量的边时,把两个根连接,恰好合并这两个集合;组内加边不改变集合划分。
- 路径压缩只把父指针改到同一条祖先链上,不改变最终根。按边加入顺序归纳,集合划分始终等于当前无向图的连通分量。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
每个节点最初独立成为一个集合。按图中边的输入顺序合并。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
while parent[node] != node:- 根的定义是父指针指向自己;不是编号最小,也不是原图中度数最大的点。
parent[node] = parent[parent[node]]- 本次让节点跳向祖父,属于路径减半,不是一次就把整条链的所有节点都改为根。
if root_a == root_b:- 相同根直接跳过,不要再次减小分量数,也不要重复把 size 相加。
parent[root_b] = root_a- 在必要的大小比较和交换后,连接两个根;随后更新胜出根的 size,count 减一。
05复杂度,来自具体的工作量
初始化 O(V),每条边调用 find 并至多一次合并。路径压缩 + 按大小合并的单次操作摊还为 O(α(V)),α 是增长极慢的反阿克曼函数。
parent 和 size 数组各有 V 项。
把工作量具体数出来
初始化 parent、size 花 O(V)。路径压缩配合按大小合并,长期操作序列中的每次操作摊还 O(α(V)),α 增长极慢,但并不是数学上严格的常数。
处理 E 条边,较精细地写为 O(V+E·α(V));宽松上界也可写 O((V+E)α(V))。不要把摊还保证说成每一次 find 都只走一步。
parent 与 size 各保存 V 项,辅助空间 O(V)。基本并查集支持不断合并,不直接支持删边后的分裂。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
合并的是根
不要直接连接任意节点,否则可能破坏集合关系。
不适合直接删边
基本并查集只适合合并;删边需离线技巧或更复杂结构。
组内加边不能再次减少组数
0–1、1–2 已让三点连通,再加入 0–2,只多出一条环上的边,连通分量仍为 1。若每条边都 count--,最终会错误得到 0。
怎样修正:只在两个根不同、确实合并了两组时减一。同一规则也可用来识别无向图中加入哪条边会形成环。
08把想法带进真实题目
自己维护分量计数
5 个独立节点,依次加入 (0,1)、(1,2)、(0,2)、(3,4)。每步分量数是多少?最后 2 与 4 是否连通?
需要一点提示
第三条边的两端已经有相同根。
查看完整推导与答案
- 初始 5 组,前两条边后分别为 4、3。
- 加入 (0,2) 不改变分组,仍为 3;加入 (3,4) 后变成 2。
- 最终两组为 {0,1,2} 和 {3,4},2 与 4 不连通。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01如何判断两个节点连通?
02路径压缩改变连通性吗?
03同集合内再加一条边,分量数怎么变?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。