第10篇并查集只保存连通分量划分。加入边可以合并集合，删除边却不能直接拆开集合：被删边可能是唯一通路，也可能还有其他路径。若全部操作预先已知，可以改变处理顺序，让每段递归只做合并，在离开时撤销这些合并。

本篇实现回滚并查集与时间线段树，回答一般无向图的离线加边、删边与连通查询。它不依赖第13篇运行程序，也不提供在线到达即回答的接口。

图边与代表元指针不是同一回事

输入有n个固定顶点，编号0到n−1，以及q个操作。每个操作为add(u,v)、remove(u,v)或query(u,v)，结果按query出现顺序返回布尔列表。所有端点先检查，越界抛IndexError；n为负、未知操作、重复添加已存在的边或删除不存在的边抛ValueError。

无向边统一为(min(u,v),max(u,v))，同一对端点同时最多存在一条边。允许自环，但自环不会改变连通性；删除后可以重新添加，形成新的生命区间。这里没有平行边引用计数，不能把重复add当作第二条独立边。

并查集的parent指针是分区表示，不要求它对应输入图中的某条边。删除图边(u,v)不能解释成“把parent[v]设回v”。例如三角形删掉一条边仍连通，这样拆分就可能产生错误答案。

先让合并可以撤销

RollbackDSU复用第10篇的find、union、connected语义，但不继承其路径压缩实现。find只沿父指针找根，不改指针。union将小集合根连向大集合根，日志记录子根、新父根与新父根原来的size。

一次成功合并只改变一个parent与一个size，因此日志保存常数个字段即可恢复。若两个端点已经同属一个集合，union返回False且不记录日志。代表元仍不承诺是最小编号。

snapshot返回当前日志长度。rollback(s)弹出直到长度为s，每弹出一项恢复两个字段。这里s是当前日志的前缀位置，不是第14篇可永久查询的版本ID；已经回滚后又建立的新分支，可能再次出现同一个长度。

回滚必须逆序，因为后一条合并可能依赖前一条合并生成的根与size。逆序恢复时，当前状态恰好回到上一条操作结束处；对弹出次数归纳即可恢复整个前缀。snapshot取长度为常数时间，rollback撤销h条日志需要O(h)，不能把两者都称为常数时间。

为什么取消路径压缩

按size合并时，一个节点的深度增加，意味着它原来所在的集合被挂到至少同样大的集合下面，新集合大小至少翻倍。当前任意合法合并前缀中，深度至多⌊log₂n⌋，所以find最坏O(log(n+1))。

回滚恢复历史size与父指针，也恢复一个原先合法的合并前缀，因此同一高度论证仍成立。union的树上工作是最坏对数次数，日志列表追加另有Python摊还成本；这里没有路径压缩带来的逆Ackermann序列界。

如果直接调用第10篇会压缩路径的find，一次查询可能改动多个parent，而常数大小的union日志没有记录它们。之后撤销union就不能恢复旧森林。可以为每次压缩写日志，但那会改变实现和复杂度证明，不能只加一个“撤销”按钮继续引用原分析。

把边的生命期放到时间轴上

操作下标为0到q−1。在时刻l添加、时刻r删除的边，其生命区间为[l,r)；一直未删除的边使用[l,q)。端点相同的多次生命期分开记录。整个历史先验证合法，之后才执行离线计算。

时间线段树的叶子对应操作时刻。把每个生命区间分解为O(log(q+1))个互不重叠的典型节点，在这些节点保存该边。这里复用11–12篇的半开区间分解，不保存求和摘要，也不调用静态RMQ。

DFS进入节点时记录snapshot，加入该节点保存的全部边；访问完子节点后回滚到snapshot。在叶子t，如果原操作是query，就查询当前并查集。按左子树再右子树访问，答案自然保持时间顺序。

同一条边可能保存在多个典型节点，但对任意一个被其生命期覆盖的叶子，根到叶路径上恰有一个这样的节点。未被覆盖的叶子路径上没有该边。因此叶子状态恰好合并了该时刻所有活跃边。

正确性分成两层

第一层是并查集：每次union恰好合并边端点所属分区，回滚准确恢复进入节点前的分区。根到叶路径以外的临时合并不会泄漏到兄弟子树。

第二层是时间分解：一条边存在于叶子状态，当且仅当该叶子的时刻落在它的生命区间中。于是叶子并查集与当前活跃图具有相同连通分量，connected返回所需答案。多余的环边即使union失败也不影响划分，自环同理。

可迁移的处理方式是“区间生效、进入应用、退出撤销”。它要求修改可逆且全部生效区间提前可知；若更新无法恢复或未来操作尚未到达，就不能直接套用这一离线结构。

与动态森林工具怎样分工

方法	维护对象与边界
Link-Cut Tree	动态森林，适合路径操作；常见splay实现为摊还对数界
Euler Tour Tree	动态森林的欧拉序列，适合子树或分量聚合；具体成本依赖序列容器
本篇回滚与时间树	预先给定的一般图操作历史，用离线顺序换取只合并与撤销

一般图维护一棵生成森林时，删除森林边后还要判断是否存在非树替代边。单独执行森林cut只断开当前森林，不足以判定原图分裂；三角形就是最小的失效边界。LCT与ETT可以成为更复杂动态图算法的组成部分，但本篇没有实现那套在线替代边搜索。

成本和实际检查

最多q段生命期，每段保存O(log(q+1))份引用，每份尝试一次union。加上初始化、扫描与查询，保守总界为O(n+q log(q+1) log(n+1))树上及容器基本操作，空间O(n+q log(q+1))。哈希字典预处理按期望成本、日志追加按摊还成本、整数位长另计；不是无条件最坏Python运行时间。

沿一条DFS路径，同时保留的成功合并至多n−1条，回滚总工作可分摊给此前成功写入的日志。输入为空时直接返回空列表，不必真正建立n个节点；保守上界仍包含初始化项。递归深度只随log(q+1)增长，不是按图上路径深度递归。

仓库根目录运行：

1	`python3 examples/advanced-algorithms/check_rollback_connectivity.py`

本次退出0：1555个合法短历史、5826个非法短历史拒绝、2955次短历史查询；另有100个固定种子随机历史和2517次查询，7次边界拒绝检查。独立参照每次query从当前活跃边重新建立邻接表并做BFS，不复用时间树或并查集。

桥删除与替代路径示例得到[True,False,True]；还检查空图、重复无向边、无效snapshot与完整恢复parent/size。实际输出保存于writing-plans/advanced-algorithms/evidence/rollback-connectivity-results.json。有限历史支持实现检查，一般正确性来自上述两层证明；没有进行在线服务或并行一致性测试。

练习

一条边先在时刻1加入、4删除，再于6加入且直到历史结束仍存在。写出两个半开生命区间，解释为什么一次snapshot不能作为两个历史状态的永久名称。
三角形0–1–2–0删去0–1后仍连通。说明并查集直接拆parent、动态森林只做cut、离线时间树三种做法分别缺少或保留了什么信息。

参考资料

UNSW COMP4128 Assignment：Part 2(a)–(b)的撤销连通性与离线区间处理。原题按添加操作ID删边；本文改用端点对并明确拒绝平行重复边。
MIT 6.851 动态图讲义：讲义封面标2012年，第1页起讨论动态森林与一般图扩展；不按URL年份推断新算法结果。
MIT Lecture 20 简介：LCT路径聚合与ETT子树聚合的职责区别。