动态图连通性问题 更新于 2026/7/3 22:21:41 作者

command_block

Loj#121. 「离线可过」动态图连通性

• 做法一 : 线段树分治 + 并查集

如果只有加边和询问连通性,可以直接使用并查集处理。

现在要求带有删除操作,套用线段树分治即可。

注意,可回退化的并查集必须采用按秩合并的形式。

总复杂度为 $O(n\log^2n)$。

评测记录

• 做法二 : LCT维护生成树

若所有边构成森林,使用 $\rm LCT$ 维护即可。

我们把某条边的边权设为其删除时间,然后维护删除时间的最大生成树。

不难发现,若两点间路径的最小值大于当前时刻,则两点连通。

复杂度 $O(n\log n)$。

[评测记录] ()

Loj#122. 「强制在线」动态图连通性

正 片 开 始 。

考虑给每条边标上一个自然数等级,称等级达到 $i$ 的边构成的图(边集)为 $G_i$ ,等级恰为 $i$ 的边集为 $L_i$。

这样,显然有 $G_0⊇G_1⊇G_2...⊇G_m$。

设 $T_i$ 为 $G_i$ 的生成森林,则可以有 $T_0⊇T_1⊇T_2...⊇T_m$。

考虑按照等级从高到低加入边来构造生成森林,显然前面加入的边不会被去掉。即 $T_i=T_0∩G_i$ ,且 $T$ 总是等级的最大生成树。

我们标定的等级需要满足如下性质 : 在 $G_i$ 中,联通块的大小均不超过 $n/2^i$ 级别。

这样,就可以证明等级大小不会超过 $O(\log n)$。

查询连通性时,只需要在 $F_0$ 上查询即可。

加入某条边时,也只需要在 $G_0$ 里面直接加入,即新边的等级为 $0$。

删除操作较为复杂。

设该边等级为 $c$ ,若其是非树边,直接将其从 $G_{0...c}$ 中删去即可。

若其是树边,按 $i=c,c-1……0]$ 的层顺序进行如下操作 :

在 $T_i$ 森林中断开该边,某棵大小不超过 $n/2^i$ 的树被分成两部分。

设较小的那一部分为 $A$ ,另一部分为 $B$ ,则 $|A|\leq n/2^{i+1}$。

$L_i$ 中和 $A$ 相连的边只有如下两种 : ① $A$ 内部的边 ; ② $A\leftrightarrow B$ 的边。

若存在其他的边,原有的生成树必然可以扩大,矛盾。

其中, $A\leftrightarrow B$ 的边的等级必然小于等于 $c$ ,否则违反最大生成树性质。

若 $i=c$ ,我们查看 $L_c$ 中的所有和 $A$ 相连的边。

若为 $A$ 内部的边,将其等级提升一级(即在 $G_{c+1}$ 中加边)

由于 $|A|\leq n/2^{i+1}$ ,该过程不会破坏连通块大小的性质。

若找到任意一条 $A\leftrightarrow B$ 的边,则停止,并在 $T_i$ 中连接该边。

若在 $L_c$ 中没有找到,则在 $L_{c-1}$ 中寻找,若找到,则对下面的每一层都执行一次加边和一次删边。

而且能够发现,由于我们每次遍历到一条无用的边,就会给该边升级,而每条边最多升至 $O(\log n)$ 级,所以总共的升级操作仅有 $O(m\log n)$ 次。

此外每一层最多一条有用的边,这部分的操作也为 $O(m\log n)$ 次。

使用 $\rm LCT$ 来维护加边操作,复杂度是 $O(m\log^2n)$ 的。

细节 :

• $\rm LCT$ 需要维护联通快大小。

• 需要一个支持 $O(\log n)$ 删掉任意一条边的边表。( 可以 map+邻接链表 )