动态图连通性问题

## [Loj#121. 「离线可过」动态图连通性](https://loj.ac/problem/121) - **做法一** : 线段树分治 + 并查集 如果只有加边和询问连通性,可以直接使用并查集处理。 现在要求带有删除操作,套用线段树分治即可。 注意,可回退化的并查集必须采用按秩合并的形式。 总复杂度为 $O(n\log^2n)$。 [评测记录](https://loj.ac/submission/539322) - **做法二** : LCT维护生成树 若所有边构成森林,使用 $\rm LCT$ 维护即可。 我们把某条边的边权设为其删除时间,然后维护删除时间的最大生成树。 不难发现,若两点间路径的最小值大于当前时刻,则两点连通。 复杂度 $O(n\log n)$。 [评测记录] () ## [Loj#122. 「强制在线」动态图连通性](https://loj.ac/problem/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+`邻接链表 )