动态图连通性问题

command_block · 2020-07-31 12:57:16 · 个人记录

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}。