SCC 的动态维护

· · 算法·理论

省流:离线分治求出每条边的闭合时刻,对时间轴扫描线,将 SCC 等效为无向图连通块。

QOJ2214 Link Cut Digraph

维护一张 n 个点初始无边的有向图,进行 m 次加边,每次操作后求出强连通点对数。

:::::success[题解]

设 T(e) 为边 e 出现时刻,f(e) 为边 e=(u,v) 端点 u \leftrightsquigarrow v 强连通的最早时刻。

对时间轴升序扫描,若 f(e) \ge T(e) 则在 f(e) 时刻加入双向边 u \leftrightarrow v。原图 SCC 等效于当前图的连通块,并查集维护 \sum \binom{\text{siz}_i}{2} 即可。

问题转化为求每条边 e 的 f 值。将操作离线后时间轴分治,设分治区间 [l,r],分治中心为 m。

对分治区间上的边 G_1=(V,E_{[l,r]}) 缩 SCC,则 u \leftrightsquigarrow v 在 G_1 中强连通当且仅当 f(e)\le m。取 e \in E 分讨:

每条边 e 只会划分到一侧,从而 \log 层分治树上 \sum |E| \le O(m\log m)。

注意精细实现,只遍历 E_{[l,r]} 端点,用 Tarjan 求 SCC 可以做到 O(|E|) 复杂度。下传右侧边时只关心 SCC 的闭合时刻,故将端点改为 SCC 标号。

总复杂度 O(m \log m)。代码。

:::::

P5163 WD与地图

维护一张 n 个点 m 条边的有向图,点有点权 a_i,支持 q 次操作:

  • 给定 u,v,删去 u \to v 的边。
  • 给定 u,\delta,令 a_u \gets a_u+\delta。
  • 给定 u,k,求 u 所在 SCC 内部前 k 大点权和。

:::::success[题解] 时光倒流变为加边。

离线分治求出闭合时刻,对时间轴扫描线,将 SCC 转化为无向图连通块。

使用并查集维护连通块,用权值线段树 / 平衡树维护连通块内前 k 大点权和,支持合并即可。

复杂度 O(q \log q+n \log^2 n)。

CF1989F Simultaneous Coloring

现有一个 n \times m 的网格,你可以将一列涂黑,或者将一行涂白。

每轮可以同时进行 k 次操作,代价为 [k>1]k^2。对于同时受到两类操作影响的格子,颜色可以自由选定。

进行 q 次操作,给定 (x,y,c),增加一条限制,格子 (x,y) 必须涂成颜色 c。每次操作后,输出满足所有要求的最小代价。

:::::success[题解]

显然行列至多操作一次。设第 i 行的操作时刻为 x_i,第 j 行的操作时刻为 y_j,钦定 (i,j) 为白等价于 x_i \le y_j,为黑等价于 x_i \ge y_j。

考虑用 n+m 个虚点代表行列,边的方向代表偏序关系。若 (i,j) 为白则连边 i \to j+n,为黑则连边 j+n \to i。

分析可得,最优策略一定是对每个 SCC 整体操作,再按缩点后拓扑序依次操作。答案即为所有 SCC 点数平方和。

离线时间轴分治求出每条边的闭合时刻 f(e),对时间轴扫描线,SCC 转化为无向图连通块,并查集用脚维护。

视 n,m,q 同阶复杂度 O(n \log n)。代码。

:::::