算法与数据结构 · 第 18 课
回滚并查集(Rollback DSU):为什么记录少量修改就能回到过去?
2026 年 11 月 6 日|第 3 周 · 第 5 天|讲授约 17 分钟(自测另计)
前两课分别处理了两类“延迟与历史”:持久化线段树通过复制路径保留多个版本,Lazy Segment Tree 则把区间修改延期下推。今天解决图上的另一个问题:已合并的连通块能不能撤销?我们会用 Rollback DSU(回滚并查集),把“恢复一个旧状态”变成撤销几条修改日志,而不是重建整个图。
一、学习目标与模型(约 1 分钟)
学完应能:(1) 理解并查集的 FIND/UNION;(2) 设计 SNAPSHOT 与 ROLLBACK;(3) 说明为何保留按大小合并,但关闭路径压缩;(4) 证明每次成功合并可在 O(1) 时间撤销、FIND 最坏 O(log n);(5) 区分“沿当前分支回滚”与“任意历史版本可并存”。
模型:顶点编号 1…n,初始每个点单独成集合。UNION(x,y) 合并连通块,CONNECTED(x,y) 检查是否同根。图为无向图;不支持直接删除任意历史边。本课支持的“删除效果”来自逆序撤销最近的成功合并。数组 parent、size 与历史栈 history 均可变;顶点数固定。
二、动机:普通 DSU 为什么不方便撤销?(约 2 分钟)
普通 DSU 只维护当前连通块。比如先连边 (1,2)、(3,4),再连 (2,3),四个顶点就连通了。如果随后想“回到插入 (2,3) 之前”,只知道现在的根还不够:必须记住合并前哪棵树是谁的孩子,以及父根之前有多大。
最直接的做法是每次保存 parent、size 的完整副本;一次快照 O(n) 时间与空间,若反复分支会很贵。更经济的想法:记录每次操作实际写过的少数几个字段,撤销时逆序恢复。
这与编辑器 Undo 很相似:并非复制整个文件,而是保存可逆修改。关键限制是必须按后进先出(LIFO)撤销,不能任意抽掉栈中间一条合并。
三、先看普通 DSU:为什么按大小合并能让树不太高?(约 2 分钟)
每个集合用一棵以代表元为根的树表示;根满足 parent[root]=root,只有根的 size 表示该集合的成员总数。FIND 沿父指针走到根,不修改沿途指针。
FIND(x):
while parent[x] != x:
x = parent[x]
return x
UNION(x,y):
a=FIND(x); b=FIND(y)
if a==b: return false
if size[a] >= size[b]: swap(a,b)
# 此时 a 的集合不大于 b
parent[a]=b
size[b]+=size[a]
components-=1
return true
翻倍论证: 一个节点的深度只有在它所在集合的根被挂到另一根下时才增加 1。按大小合并意味着新集合至少有旧集合的两倍大。一个节点所在集合的大小从 1 开始,最多到 n;它的深度最多增加 ⌊log₂n⌋ 次。所以即使没有路径压缩,FIND 仍有确定性的最坏 O(log n) 时间。
删除/回滚不会破坏这个界:撤销后回到某个合法的、按大小合并构成的状态;在该状态继续按大小合并,仍满足同一翻倍分析。
四、用历史栈实现快照与回滚(约 3 分钟)
对一次真正成功的合并,只记录三项:被挂上的小根 a、接纳它的大根 b、修改前的 size[b]。撤销时无需保存整个 parent 数组:合并前 a 就是根,所以旧值必为 parent[a]=a。
INIT(n):
for i=1..n: parent[i]=i; size[i]=1
components=n
history=[]
FIND(x): # 绝不做路径压缩
while parent[x]!=x: x=parent[x]
return x
UNION(x,y):
a=FIND(x); b=FIND(y)
if a==b: return false # 无修改,不压栈
if size[a]>=size[b]: swap(a,b)
history.push((a,b,size[b])) # 修改前记录旧值
parent[a]=b
size[b]+=size[a]
components-=1
return true
SNAPSHOT():
return len(history) # O(1),返回当前分支的栈长度
ROLLBACK(s): # s 必须是当前分支的有效祖先快照
assert 0<=s<=len(history)
while len(history)>s:
(a,b,oldSizeB)=history.pop()
parent[a]=a
size[b]=oldSizeB
components+=1
这里刻意不压栈记录失败合并,因为它没改任何结构。SNAPSHOT 返回的是“成功合并历史栈的长度”,不是时间戳,也不是全局唯一版本号。对一个合法的祖先快照 s,ROLLBACK(s) 会撤销当前分支中此后发生的所有成功合并。
每次记录都在写入前完成;ROLLBACK 时按逆序弹出,保证被撤销合并之后产生的修改都已经先恢复。若把栈里的中间记录直接删除,就没有这种保证。
五、完整 Trace:合并、快照、撤销、再分叉(约 3 分钟)
设 n=6。为了让父指针易读,两个集合大小相等时约定“第一个 FIND 得到的根做父根”(上述伪代码在 size[a]>=size[b] 时交换,保证相等时原先第一个根成为父根);不影响集合划分与复杂度。
| 步骤 | 操作 | history 长度 | components | 连通块 |
|---|---|---|---|---|
| 0 | INIT(6) | 0 | 6 | {1},{2},{3},{4},{5},{6} |
| 1 | UNION(1,2) | 1 | 5 | {1,2},{3},{4},{5},{6} |
| 2 | UNION(3,4) | 2 | 4 | {1,2},{3,4},{5},{6} |
| 3 | s=SNAPSHOT() | 2 | 4 | 保存回滚位置 s=2 |
| 4 | UNION(2,3) | 3 | 3 | {1,2,3,4},{5},{6} |
| 5 | UNION(5,6) | 4 | 2 | {1,2,3,4},{5,6} |
| 6 | UNION(4,5) | 5 | 1 | {1,2,3,4,5,6} |
| 7 | UNION(1,6) | 5 | 1 | 已连通,没产生历史记录 |
| 8 | ROLLBACK(s) | 2 | 4 | {1,2},{3,4},{5},{6} |
| 9 | UNION(4,5) | 3 | 3 | {1,2},{3,4,5},{6} |
以第 4 步为例:旧根 1 的 size=2、旧根 3 的 size=2;合并时把根 3 挂到根 1,保存 (3,1,2)。第 6 步之后,回滚到 s=2,按顺序撤销“把 5 挂到 1”“把 6 挂到 5”“把 3 挂到 1”;因此恢复为四个连通块。第 9 步是在恢复状态上新建的分支,而不是接着旧状态继续。
flowchart TD
S["快照 s=2:{1,2} / {3,4} / {5} / {6}"]
S --> A["UNION(2,3) → 合并两对"]
A --> B["UNION(5,6) → 合并 5 与 6"]
B --> C["UNION(4,5) → 六点连通"]
C --> D["ROLLBACK(2):逆序撤销三条成功合并"]
D --> S
S --> E["新分支:UNION(4,5)"]
E --> F["{1,2} / {3,4,5} / {6}"]
示意图的限制: 图中从快照向两边分叉是“逻辑上的执行轨迹”;本算法只维护当前一份可变状态,不会像持久化线段树一样同时在内存里保存可直接查询的两份完整当前状态。
六、两个不变量与正确性证明(约 2 分钟)
连通性不变量 I: parent 构成若干棵无环根树;每棵根树恰代表一个连通分量,size[root] 是该分量的节点数;components 是根树个数。
初始化各自成树,显然成立。UNION 对两个不同根只添加一条从小根指向大根的父指针,不会造环;原来两个分量变成一个,根的 size 加上另一棵树大小,components 减 1。若已同根,什么也不变。
可撤销不变量 II: history 中每条成功合并记录都准确描述当时改动的 parent、size、components,且栈顺序与修改顺序一致。由于 ROLLBACK 总是弹出最新记录,当处理记录 (a,b,oldSizeB) 时,之后的所有结构变化已撤销,a 再次是 b 的直接子根。于是把 parent[a] 设回 a、size[b] 恢复旧值、components 加 1,准确得到合并前状态。
对撤销条数归纳,ROLLBACK(s) 恰好恢复快照时的森林和连通分量划分,FIND/CONNECTED 的结果因此正确。这里不仅要证明“当前连通性正确”,还要证明每次逆操作恢复了以后还会用到的 size,否则下一次按大小合并可能在错误的数据上运行。
七、关键反例:为什么这里不能随手加路径压缩?(约 2 分钟)
普通 DSU 常写 parent[x]=FIND(parent[x]),把路径直接缩到根。它可加速未来查询,却会修改额外父指针;若这些写入不记录到 history,回滚 UNION 就可能不再正确。
取四个点,先 UNION(1,2)、UNION(3,4),形成 parent[2]=1、parent[4]=3。此时 SNAPSHOT。再 UNION(1,3),使 parent[3]=1。调用带路径压缩的 FIND(4),把 parent[4] 从 3 改成 1。
合并前: 1 ← 2 3 ← 4
临时合并: 1 ← 3 ← 4 且 1 ← 2
压缩 FIND(4) 后:parent[4]=1
仅撤销临时 UNION(1,3):parent[3]=3
但 parent[4] 仍等于 1 ! # 错把 4 与 {1,2} 连通
所以本课选择“无路径压缩 + 按大小合并”:在保证 O(log n) 高度的同时,所有结构写入都集中在成功 UNION 的常数个字段,容易严格回滚。理论上可以记录路径压缩的每次指针修改再回滚,但日志与操作成本会不同,不属于这套 O(1) 撤销单次成功合并的设计。
八、复杂度、适用边界及与持久化的区别(约 1 分钟)
| 操作 | 最坏时间 | 原因 |
|---|---|---|
| INIT | O(n) | 初始化 parent、size |
| FIND / CONNECTED | O(log n) | 按大小合并保证树高对数 |
| UNION | O(log n) | 两次 FIND + O(1) 修改和记录 |
| SNAPSHOT | O(1) | 只返回 history 长度 |
| ROLLBACK(s) | O(k) | 撤销 k 条成功合并,每条 O(1) |
| 当前状态的总空间 | O(n) | 两个数组和至多 n−1 条尚未撤销的成功合并记录 |
对 n=1,上面的对数界可统一写作 O(1+log n)。这里的 k 是需要实际撤销的成功合并数,不是从快照以来执行的 FIND 或失败 UNION 次数。
边界 1: 这不是支持“删除任意一条旧边”的在线动态连通性结构;只能沿当前历史栈逆序撤销合并。边界 2: 一旦回滚到较早快照再走另一分支,旧分支的栈长度不能作为永久版本标识;必须限制只回滚当前分支上的有效祖先快照。边界 3: SNAPSHOT 是 O(1) 并非保存了整份 parent;不能同时对多个已离开的版本做任意查询。
对比第 16 课:路径复制持久化的旧根一直可用,支持不同版本并存、从任意旧根再次分叉;Rollback DSU 只维护一份当前状态,沿 DFS 执行路径“进入分支 → 修改 → 查询 → 回滚”,空间和实现都更经济,但不能同时直接查询兄弟分支。这正是它在离线动态连通性中常见的原因。
九、今日小结与下一课
核心链条:
[ \text{按大小合并} \Rightarrow \text{树高 }O(\log n) \Rightarrow \text{无路径压缩仍可高效 FIND} \Rightarrow \text{每次成功 UNION 只改常数个字段} \Rightarrow \text{LIFO 回滚每条 }O(1). ]
下一课(2026-11-07,第 19 课):离线动态连通性。 把边的存在时间分解到“时间线段树”,在 DFS 进入节点时 UNION、退出时 ROLLBACK。届时我们会看到:如何用今天的栈式回滚,在存在加边和删边的整个时间轴上回答连通性查询。
十、四级自测(总分 100;首次不公布答案)
前 3 题客观判分,最后一题按完整证明分步评分。题目覆盖不同知识维度,下面只提供中立提示。
Lv1|无路径压缩与回滚机制|15 分|预计 2 分钟|单选
回滚并查集使用按大小合并,并且历史栈只记录真正发生的合并。下列哪项严格正确?
A. 为了保持接近常数的 FIND,必须开启路径压缩;仅记录 UNION 的修改即可安全回滚。
B. 关闭路径压缩、保留按大小合并时,FIND 最坏 O(log n);撤销一次成功合并只需 O(1)。
C. SNAPSHOT 必须复制完整 parent 和 size 数组,否则不能回到旧状态。
D. 两点已经连通时,UNION 仍必须往历史栈压入一条成功合并记录,否则快照必定失效。
中立提示:把 FIND 是否改写 parent、一次合并实际修改哪些字段、SNAPSHOT 记录什么三件事分开检查。
Lv2|多次 UNION 与 ROLLBACK 的分支 Trace|20 分|预计 4 分钟|单选
初始有 1…7 七个孤立顶点。依次 UNION(1,2)、UNION(3,4),记 s=SNAPSHOT();随后 UNION(2,3)、UNION(5,6)、UNION(4,5)、UNION(1,6);执行 ROLLBACK(s);最后 UNION(2,7)、UNION(4,6)。问最终的连通分量划分是什么?(按大小合并,若大小相等可任选根;分量划分不依赖根的选择。)
A. {1,2,3,4,5,6,7}
B. {1,2,7}、{3,4,6}、{5}
C. {1,2,7}、{3,4}、{5,6}
D. {1,2}、{3,4,6}、{5,7}
中立提示:先停在快照时刻,明确之后哪些合并应被整体撤销;最后两次 UNION 是在恢复出的状态上建立新分支。
Lv3|复杂度证明与历史快照边界|25 分|预计 4 分钟|多选
针对只支持沿当前执行分支回滚到有效祖先快照的 DSU,以下哪些说法成立?(多选,选出全部正确项)
A. 不使用路径压缩而采用按大小合并时,每当某节点深度因合并增加,其所在连通分量规模至少翻倍,因此最坏树高 O(log n)。
B. 若只为成功合并压栈,SNAPSHOT 返回历史栈长度,ROLLBACK(s) 持续撤销到该长度,可以恢复当前分支中对应快照的状态。
C. FIND 的路径压缩不影响连通性,因此无需记录其 parent 修改,单靠 UNION 历史就能保证回滚后连通性正确。
D. 回滚到较早快照、再从该状态建立另一分支后,旧分支缓存的任意快照编号仍能唯一标识原来的历史状态。
中立提示:注意“集合划分不变”不代表“未来撤销时结构仍能恢复”;也区分快照栈长度与永久版本标识。
Lv4|算法设计、不变量证明和压缩反例|40 分|预计 10 分钟|开放推导
设计支持 INIT(n)、FIND(x)、UNION(x,y)、SNAPSHOT()、ROLLBACK(s) 的回滚并查集,要求只能沿当前执行分支回到有效祖先快照,顶点编号为 1…n。(a)(12 分)写出按大小合并、无路径压缩的伪代码,明确成功与失败合并怎样记录历史,快照与撤销怎样恢复 parent、size、components;(b)(10 分)陈述并证明连通分量划分不变量与 LIFO 回滚的正确性;(c)(10 分)严格推导 FIND/UNION/SNAPSHOT/ROLLBACK 的最坏时间和空间界,并解释为什么在该设计中不能直接使用普通路径压缩;(d)(8 分)给出至少四个顶点的具体操作序列,展示若 FIND 执行路径压缩却不记录其修改,回滚后可出现错误连通;最后说明它与路径复制持久化的能力区别。
中立提示:成功合并前记录小根、大根及大根旧 size;撤销必须倒序。构造路径压缩反例时,让一个非根节点先经过中间根连到另一棵树,再压缩、撤销中间根的合并。
十一、提交与反馈
请回复 Lv1:选项;Lv2:选项和关键分量;Lv3:全部正确选项;Lv4:(a)–(d) 分步推导。我会按 15/20/25/40 分逐题批改。80–100 分按原进度继续;60–79 分补一道针对练习;低于 60 分优先复习“历史栈 LIFO”“按大小合并高度证明”“路径压缩破坏回滚”的机制。补练不改变自然日课号。