离线动态连通

时间区间化 ​

预先读取 $q$ 个 add、remove、query 操作。对每个带身份的无向边配对插入与删除，得到半开活跃区间 $[l,r)$；直到结尾未删除的边取 $r=q$。把每个区间分解成时间线段树的 $O(\log q)$ 个完全覆盖节点。

DFS 不变量 ​

深搜时间树时，在进入节点时把该节点所有边 union 到可回滚 DSU公理库可回滚并查集rollback DSU · undoable union-find把每次合并修改压栈，以快照栈长度为边界撤销最近更新的并查集。。不变量是：到达代表时刻 $t$ 的叶时，DSU 恰含所有覆盖根到叶路径的边，也就是 $t$ 时活跃图。叶上用 Find 回答 query；离开节点时回滚到进入前快照。

若每次 DSU 操作为 $O(\log n)$，每条边进入 $O(\log q)$ 个节点，总时间为

$$O((m\log q+q)\log n),$$

另加区间构建成本。

重边例子 ​

同一端点对可能被添加两次再删除一次。若只用端点对作布尔状态，第一次删除会错误地让边完全失活；应按边 ID 配对，或维护每对端点的引用计数并只在计数从 0/到 1 时改变连通图。

模型边界 ​

算法依赖已知未来删除时间，是 offline 而非在线 fully dynamic connectivity。区间端点若混用闭区间，会让删除时刻多保留一轮。它只回答连通性等可由 DSU 合并维护的性质；带删除的最短路不能机械套用。

预处理与空间 ​

扫描操作序列时，为每个边身份保存尚未配对的 add 时间栈；remove 弹出最近匹配时间并产生区间。若语义禁止重复激活，同一边二次 add 应报错而非悄悄覆盖。每个区间在线段树中存 $O(\log q)$ 份，空间 $O(m\log q+q)$。

时间分治可不用显式线段树：递归处理中点，把跨越整个子区间的边加入 DSU，其余区间下放孩子。两种写法共享“根叶路径恰含当前活跃边”的不变量，复杂度相同量级。

从操作流生成活跃区间 ​

扫描时间 $0,\dots ,q-1$，对每条无向边用规范端点 (min(u,v), max(u,v)) 作为键。add 把当前时刻压入该键的栈，remove 弹出最近一次加入并生成半开活跃区间 $[t_{add},t_{remove})$；扫描结束仍在栈中的加入生成 $[t_{add},q)$。这套配对也自然支持重边。

每个区间被放进时间 segment tree 的 $O(\log q)$ 个 canonical 节点，因此总存储和 union 次数为 $O(a\log q)$，其中 $a$ 是活跃区间数。DFS 到时刻叶子时，路径上恰含该时刻所有有效边；回退节点前回滚快照，便不会把兄弟时间段的边泄漏过来。

总复杂度通常写成 $O((a\log q+q)\log n)$，最后一个 $\log n$ 来自无路径压缩的 rollback DSU。若只报 $O(q{\log }^{2}q)$，就隐含了 $n,q$ 同阶且忽略重边区间数；模型变化时该简写可能误导。

参考资料

• David Eppstein et al., Sparsification—A Technique for Speeding Up Dynamic Graph Algorithms, JACM, 1997.
• Erik Demaine, MIT 6.851 Dynamic Graph Algorithms, offline connectivity notes.