全动态连通性

在线模型与选定保证 ​

维护固定顶点集 $V$ 上的无向简单图，$n=|V|$。更新为 insert$(e)$ 或 delete$(e)$，查询 connected$(u,v)$ 必须在看不到未来操作的在线条件下立即回答。以下讲 Holm–de Lichtenberg–Thorup（HDT）确定性框架的一个标准实现：

$$\begin{array}{cc}\text{操作}& \text{保证}\\ \text{预处理/空间}& O(n)\text{与}O(n+m)\text{words}\\ \text{connected}& O(\log n)\text{最坏}\\ \text{insert/delete}& O({\log }^{2}n)\text{摊还}\end{array}$$

其中 $m$ 是当前边数，生成森林由 Euler Tour Tree公理库Euler Tour TreeEuler tour tree · ET-tree · 动态 Euler Tour Tree将无向树的 Euler 环游维护为可 split、join 的平衡序列，以支持动态森林的换根、连边、断边、连通性和分量聚合。维护。原论文与后续实现可进一步改善查询或常数；这里固定上述版本，不把 connectivity、动态最小生成树和二边连通的不同界拼在一起。

删除树边为何困难 ​

只插边时，并查集可合并分量；删除一条非树边也不改变现有生成森林。困难发生在删除生成树边 $e$：森林立刻裂成 $A,B$ 两棵树，但原图是否断开取决于所有非树边中是否存在一条跨越割 $(A,B)$ 的 replacement edge。

从头扫描全部边能找到 replacement，却可能每次花 $\mathrm{\Theta }(m)$。HDT 的目标不是消除搜索，而是保证同一条失败候选只会在有限多个层级被重新扫描。

层级与森林不变量 ​

每条边 $e$ 有层级

$$\ell (e)\in \{0,1,\dots ,L\},L=\lfloor {\log }_{2}n\rfloor .$$

令 $G_i$ 含所有层级至少 $i$ 的边，并维护一组嵌套生成森林 $F_i$，使 $F_i$ 是 $G_i$ 的 spanning forest，且

$$F_L\subseteq F_{L-1}\subseteq \cdots \subseteq F_0.$$

关键大小不变量是：$F_i$ 的每个连通分量至多含 $n/2^i$ 个顶点。新边从 level $0$ 开始。每个 ETT 节点还按层级维护关联非树边，以便枚举某一分量在指定 level 的候选。

插入 $(u,v)$ 时，若 $u,v$ 在 $F_0$ 中不连通，就把边作为 level-0 tree edge 加入相应森林；否则记为 level-0 non-tree edge。删除 non-tree edge 只需从其边集合移除。

replacement 搜索与提升 ​

删除 level $i$ 的 tree edge 后，相关森林裂成两侧。算法从 level $i$ 向低层处理，并总选顶点数较少的一侧 $A$ 搜索 level-$i$ 非树边：

• 若边 $(x,y)$ 的两端已在同一侧，它不能替换当前割；把它提升到 level $i+1$，以后不再在本层扫描。
• 若边跨越两侧，它成为 replacement tree edge，并在所有需要的低层森林中重新连接两棵树。
• 若本层没有跨割边，把较小侧中相应 level-$i$ tree edges 一同提升，使 $F_{i+1}$ 的分量大小不变量继续成立，再到下一层寻找。

之所以总看较小侧，是因为它至多占原分量一半；提升后，该边所在的更高层分量仍满足 $n/2^{i+1}$ 的规模上界。Replacement 搜索不是“随便挑一条非树边”：边在哪些 $F_i$ 中作为 tree edge、在哪个层级的邻接集合中作为 non-tree edge，必须同步维护。

摊还分析 ​

边的层级只增不减，最多从 $0$ 提升到 $L$，所以每条边一生至多被成功提升 $O(\log n)$ 次。一次在 ETT 中检查、删除、提升或 link/cut 一条候选花 $O(\log n)$；把扫描成本记到账到被提升的边，全部更新上的总提升成本为

$$O(m_{\mathrm{life}}{\log }^{2}n),$$

其中 $m_{\mathrm{life}}$ 是操作序列中曾插入边的总数。其余每次更新只做每层常数次森林操作，仍落在 $O({\log }^{2}n)$ 摊还界内。

这不是单次最坏界：一次不幸的 tree-edge 删除可能检查许多候选，成本由那些候选以后不再停留在同一层这一事实偿还。若实现允许边层级下降，上述记账立即失效。

具体例子：三角形中的 replacement ​

图含三角形 $a-b-c-a$。生成森林当前选 $ab,bc$，边 $ac$ 为 level-0 non-tree edge。删除 tree edge $ab$ 后，ETT 把森林分成 $\{a\}$ 与 $\{b,c\}$；扫描较小侧 $a$ 的 incident non-tree edges 时发现 $ac$ 跨割，于是把它转为 tree edge，图仍连通。

若另有许多边都只连接 $\{b,c\}$ 内部，它们对该割无用。算法扫描到这种内部边时把它提升；将来同层发生相似删除时，不会再次为同一条失败边付费。

失败边界与模型区分 ​

离线动态连通公理库离线动态连通offline dynamic connectivity把边的活跃时间区间分配给时间线段树，并用可回滚并查集回答离线连通查询。预先知道每条边的活跃时间，可用时间线段树和 rollback DSU；HDT 不知道未来删除时刻，付出更复杂的分层 replacement 搜索。把离线总时间除以操作数不能得到在线 update bound。

本页只维护无向连通性。带权 replacement edge 要按权值选择，会进入 fully dynamic minimum spanning forest；判断桥、二边连通或有向强连通也需要更强不变量。多重边版本可以支持，但必须给每个边实例独立身份，否则删除其中一条会误删其余平行边。

参考资料

• Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup, “Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity,” JACM 48(4), 2001.
• David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig, “Sparsification — A Technique for Speeding Up Dynamic Graph Algorithms,” JACM 44(5), 1997.
• Monika R. Henzinger and Valerie King, “Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation,” JACM 46(4), 1999.