点双连通分量的求法

由于我水平太低普及组知识点都没掌握,今天终于搞懂了一点所以打算记录一下。

下面讨论的都是无向图,由于连通块间独立,我们只考虑连通图的情况。

如果点数为 \(1\),在某些问题下需要特殊处理。下面我们只考虑点数不为 \(1\) 的情况。

定义 1 对于一个连通图 \(G\),如果从 \(G\) 删去点 \(u\) 和所有与它相邻的边得到的图不连通,就称 \(u\)\(G\) 的一个割点。

定义 2 若连通图 \(G\) 中不存在割点,则称 \(G\) 是一个点双连通图。

定义 3 称连通图 \(G\) 的极大点双连通图子图为 \(G\) 的点双连通分量。

性质 1 两个不同点双连通分量的交至多包含一个点。

证明 假设两个不同的点双连通分量 \(A\)\(B\) 有交,设这两个点双连通分量的并为 \(H\),根据点双连通分量的定义,\(H\) 一定不是点双连通图,所以存在一个点 \(u\),从 \(H\) 中删去点 \(u\) 后得到的图不连通。\(H\) 中删去点 \(u\) 得到的图即为 \(A\) 删去点 \(u\) (如果存在) 和 \(B\) 删去点 \(u\) (如果存在) 得到的图的并。如果 \(A\)\(B\) 的交大于 \(1\),由于两个有交的连通图的并仍为连通图,\(H\) 中删去点 \(u\) 得到的图也是连通图,这就导出了矛盾。

性质 2 在一个连通图 \(G\) 中,对于任意一条边 \(e\),恰有一个 \(G\) 的点双连通分量包含边 \(e\)

证明\(e\) 的两个顶点的导出子图就是一个 \(G\) 的大小为 \(2\) 的点双连通子图,所以也一定存在包含边 \(e\) 的点双连通分量。由性质 1 可知两个不同的点双连通分量不可能包含同一条边。

由于点双连通分量是连通的,只要确定了一个点双连通分量中所有边,点也就确定了。图 \(G\) 的所有点双连通分量构成边集的一个划分。

在图上作 DFS,取一棵以 \(r\) 为根的 DFS 树,设点 \(u\) 第一次被访问时间为 \(dfn_u\)\(u\) 子树中所有点通过一条返祖边能够到达的 dfn 最小的点的 dfn 与 \(dfn_u\) 的最小值为 \(low_u\) (注意返祖边指的是非树边,不包含 \(u\) 到父亲的边,实现时要特判)。

设点 \(u\) 在这棵 DFS 树上的父亲为 \(fa(u)\)

对于点 \(u \neq r, fa(u) \neq r\),如果 \(low_u < dfn_{fa(u)}\),那么存在一个包含点 \(u, fa(u), fa(fa(u))\) 的点双连通子图,从而 \(u\) 到父亲的边和 \(fa(u)\) 到父亲的边在同一个点双连通分量中。

在 DFS 的过程中,每经过一条树边就把这条树边放入一个栈中。在点 \(u\) 回溯时,检查一下是否有 \(low_u \ge dfn_{fa(u)}\) (如果是根的话不用检查了)。

考虑第一次满足这个条件的回溯,此时点 \(u\) 子树中所有树边都在同一个点双连通分量中,因此存在一个包含 \(u\) 子树中所有点的点双连通子图。因为不存在跨过 \(u\) 到父亲的边的非树边,这个点双连通子图是一个极大点双连通子图,所以 \(u\) 的子树中所有点的导出子图是一个点双连通分量。我们把这个点双连通分量中的点保存起来,然后从栈中弹出 \(u\) 子树中所有树边。

在之后的回溯中,如果满足 \(low_u \ge dfn_{fa(u)}\),那么此时栈中所有树边在同一个点双连通分量中,且这些边的所有端点的导出子图是一个点双连通分量。把这个点双连通分量保存下来然后把栈中所有 \(u\) 子树中的边弹出即可。

这样就在 \(\mathcal O(n+m)\) 的复杂度内求出了每个点双连通分量的点集。一个点双连通分量中的边就是这个点双连通分量内部的树边加上这个点双连通分量中所有点的返祖边,这很容易处理。(注意这里返祖边的定义是从某个点出发到它祖先的非树边,这也就意味着每条非树边是恰好一个点的返祖边)