离线动态连通

删除之所以难，是因为普通并查集只会合并，不能把一条旧边从当前状态抽走。离线视角把“边何时存在”提升为一条时间区间：时间树把区间拆成若干完整覆盖块，DFS 进入块时加入边、离开块时撤销。于是数据结构始终只做擅长的合并与栈顶回滚，却能在每个叶子重现那个时刻的整张活跃图。

分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。和线段树是同一时间递归的两种写法。显式线段树先保存规范节点；递归写法在区间中点处分配覆盖整个子问题的边，再把其余区间下放两个孩子。两者共享“根叶路径恰含当前时刻所有活跃边”的不变量。

重边与引用计数 ​

同一端点对可能连续添加两次，再只删除一次。若把端点对当作布尔状态，第一次删除就会错误地让边完全失活。可以按边 ID 分别配对，也可以维护端点对引用计数：计数从 $0$ 变为 $1$ 时开始一段连通图活跃区间，从 $1$ 变为 $0$ 时才结束；中间的增加和减少不改变“至少有一条边存在”这一连通事实。

采用栈配对时，remove 应弹出最近一次未匹配 add。若操作语义指定特定边 ID，就必须按该 ID 删除，不能用任意 LIFO 配对代替。删除不存在的边、扫描结束仍有未配对 add，以及闭区间/半开区间混用，都应在预处理阶段明确处理。

模型边界 ​

算法依赖预先知道未来删除时刻，是 offline 方法，不是在线 fully dynamic connectivity。半开区间 $[l,r)$ 确保边在 remove 时刻已经失效；若误用闭区间，会多保留一次查询。该框架适合连通分量数、二分图 parity 等能随 union 增量维护且可回滚的摘要；带删除最短路没有同样的合并不变量，不能机械套用。

预处理保存每个边身份的 add 栈、$a$ 个活跃区间和时间树节点列表，总空间为 $O(a\log q+q+n)$；DFS 同时存在的 DSU 历史只对应当前根叶路径上的成功合并与附加摘要。若每个分量还维护大小、奇偶势或权重和，union 时必须把所有被覆盖字段一并压入回滚记录。

离线动态连通常作为“时间分治 + 可撤销状态”的标杆：同一结构还能处理区间生效约束、批量版本验证和某些离线二分图查询。若更新必须到来即答，或需要最坏/摊还多对数更新时间，则要转向 Euler-tour tree、link-cut tree 或分层动态森林等在线结构；这些算法不能从本页的预知未来假设直接推出。