可回滚并查集

状态与接口 ​

使用 union by size/rank，不做路径压缩。Find 沿父指针到根，树高 $O(\log n)$。成功合并根 $a,b$ 时，把被改根的旧 parent、接收根的旧 size 及需要维护的分量数压入历史栈；snapshot 返回当前栈长度 $s$，rollback$(s)$ 逐项恢复直到栈长为 $s$。

不变量与复杂度 ​

每条历史记录恰好描述一次可逆原子修改，按逆序恢复后，父森林、size 和附加摘要都回到快照状态。Union、Find 最坏 $O(\log n)$；撤销成本与实际弹出的记录数线性，若一次 union 只写常数字段，则撤销该 union 为 $O(1)$。

递归搜索例子 ​

在分治递归节点加入一批当前区间有效的边，进入孩子前保存栈长；孩子处理完 rollback 到该长度。左右孩子因此共享父节点状态，却不会互相泄漏修改。这比复制整个 DSU 状态节省空间和时间。

易错边界 ​

重复 union 两个已连通顶点不改变结构，但快照语义必须一致：可压一个 no-op 标记，或只以栈长度回滚并确保调用方不按 union 次数撤销。路径压缩会修改整条路径，若不逐项记录就无法恢复。rollback 只能撤销栈顶历史；任意版本查询属于持久化，任意过去编辑属于追溯结构公理库追溯数据结构retroactive data structure · retroactivity允许在操作时间线的过去插入或删除更新，并重新解释其后状态的数据结构模型。。

可回滚摘要 ​

若每个分量还维护权重和、二分图 parity 或最小编号，union 时必须把所有被覆盖字段的旧值一并压栈。恢复顺序与写入相反，且只把小根挂到大根，保证 Find 最坏 $O(\log n)$。以分量和为例，合并前记录大根旧 sum，回滚后既恢复 parent/size，也恢复 sum；只撤父指针会留下跨分量污染。

历史栈空间与成功合并次数及附加字段数线性。深度优先分治中最大同时栈长通常为当前根叶路径所加入边数，而非所有递归节点边副本之和。

栈中究竟记录什么 ​

执行 union(a,b) 前先找两根 $r_a,r_b$。若相同，也要推入一个 no-op 标记，保证“调用次数快照”能一致回滚；若不同，令小树根挂到大树根，并把 (被挂根, 旧父亲, 新根, 旧大小) 推栈。恢复时按相反顺序写回，不能重新调用 union 猜测旧状态。

一次递归搜索的状态轨迹是：

1. snap = history.length；
2. 应用当前节点代表的所有边；
3. 递归访问子问题并回答叶查询；
4. rollback(snap)，逐项弹栈到原长度。

按大小合并使 find 最坏 $O(\log n)$，成功 union 改常数字段，回滚每条记录 $O(1)$。若额外维护连通分量数、二分图奇偶势或分量和，也必须把每个被改摘要的旧值纳入同一记录；否则父指针恢复了，查询语义仍留在未来状态。

参考资料

• James Driscoll et al., Making Data Structures Persistent, JCSS, 1989.
• Erik Demaine, MIT 6.851 Dynamic Graphs Notes, rollback union-find.