可回滚并查集 | Codeboy's Blog

形式陈述

可回滚并查集以并查集的前向 find/union 接口为基础，增加按更新栈逆序撤销的操作。前向步骤合并块，撤销则恢复某个历史划分，可能把块重新分开；恢复范围由已保存的历史限定。对固定全集，若调用者只使用前向 find/union 而不调用回滚，就得到普通并查集的只合并接口；额外的历史恢复能力不会改变这些前向操作的含义。

状态与接口

维护 parent、size 和连通分量数，采用按大小合并，不做路径压缩。find 沿父指针到根；union(a,b) 先找两根，若不同，就把较小树根挂到较大树根，并向历史栈写入一条记录，保存被改根的旧 parent、接收根的旧 size 和旧分量数。若两根相同，普通连通性版本没有修改，也不压入记录。

snapshot() 返回当前栈长度 $s$ ；rollback(s) 逐条弹出并恢复，直到栈长为 $s$ 。这里的快照只指向当前历史的一个祖先前缀。回退后走入另一个分支，旧分支中的长度数字不再是可随意访问的版本标识；即使新栈后来再次达到相同长度，也未必代表旧状态。

不变量与复杂度

每条记录保存一次成功合并覆盖的全部字段，逆序恢复便同时还原父森林、分量大小和分量数。按大小合并时，一个顶点每增加一层深度，其所在分量至少翻倍，所以合法状态下树高为 $O(\log(n+1))$ ；回滚恢复的也是曾经满足此不变量的状态。

初始化 $n$ 个单元素集合需 $\Theta(n)$ 时间。find、union 最坏为 $O(\log(n+1))$ ，快照为 $O(1)$ ；弹出 $r$ 条记录的回滚为 $O(1+r)$ 。若一次合并只改常数字段，撤销它本身为 $O(1)$ 。普通版本的当前栈至多有 $n-1$ 次成功合并，故包含数组在内的空间为 $O(n)$ ；空集合不允许调用带元素参数的操作。

直觉

Rollback DSU 牺牲路径压缩，让每次 union 只改常数字段，并把旧值按时间顺序压栈。快照只是一个栈长度；递归分支退出时逆序恢复到该边界，便能共享父状态而让兄弟子问题彼此隔离。

例子与边界

兄弟分支共享起点

从 $\{1\},\{2\},\{3\},\{4\}$ 开始，保存快照 $s_0=0$ 。合并 $1,2$ 后保存 $s_1=1$ ，再合并 $2,3$ ，栈长变成二，前三点连通。回滚到 $s_1$ 后， $1,2$ 仍连通， $3$ 恢复独立。

现在改为合并 $3,4$ ，栈长又是二，但当前分区是 $\{1,2\},\{3,4\}$ ，并不是旧分支的 $\{1,2,3\},\{4\}$ 。这说明栈长度是当前递归历史的恢复边界，不是可永久保存的任意版本编号。最后回滚 $s_0$ ，四个单点全部恢复。

无修改调用与路径压缩

重复 union(1,2) 若两点已连通，不写记录，也不改变任何既有快照。调用方必须按栈长度回滚，不能把“弹一条记录”误当成“撤销最近一次 union 调用”。若另行提供按调用次数撤销的接口，才需要给无修改调用加入标记，并相应计算更多历史空间。

普通路径压缩会沿查找路径改写多个 parent；没有逐项记账就无法恢复，而完整记账后的成本也需要重新分析。本页的最坏树高与常数合并记录保证来自“按大小合并、无路径压缩”这一明确组合。

任意旧版本查询属于持久化，任意过去编辑属于追溯结构；本接口只允许沿当前历史逆序退回。

推论与应用

可回滚的递归状态

时间分治或搜索树的一次调用可按以下次序进行：

记录 snap = history.length；
应用当前节点代表的全部合并；
递归访问子问题，或在叶子回答查询；
执行 rollback(snap)。

每个孩子都用相同方式恢复自己的修改，因此兄弟分支共享父状态却彼此隔离。历史栈只保存当前根叶路径上尚未撤销的修改，无须为整棵递归树复制全部 DSU。

摘要必须一起恢复

若每个分量还保存权重和、最小编号或其他固定大小摘要，成功合并时也须保存所有被覆盖字段。例如只还原 parent 和 size，却留下合并后的 sum，会让已经拆开的分量仍返回混合权重。

奇偶约束还多一项边界：即使两端已在同一分量，加入一条边也可能揭示奇环，改变“当前是否二分”或矛盾计数。这种同根更新同样必须入历史，不能沿用普通连通性版本的无修改分支。带这些扩展时，空间应按实际未撤销的修改条数计算，而不再只按成功合并次数计算。

参考资料

James Driscoll et al., Making Data Structures Persistent, JCSS, 1989.
Erik D. Demaine, MIT 6.851 Advanced Data Structures, dynamic-graph notes on rollback union–find, accessed 2026.

形式陈述 ​

状态与接口 ​

不变量与复杂度 ​

兄弟分支共享起点 ​

无修改调用与路径压缩 ​

可回滚的递归状态 ​

摘要必须一起恢复 ​