有向图的双连通性

未分类

---

支配树

支配性是这样一种问题：
如果源点 $S$ 到 $u$ 的每条路径上都有 $v$ ，则称 $v$ 支配 $u$ （ $v$ 是 $u$ 的支配点 ）。

为了解决有向图上的支配性问题，类似在无向图上的做法，我们从 dfs 树上开始入手。

定义 $\mathrm{idom}(u)$ 是 $u$ 的支配点（在 dfs 树中，下同）深度最大的一个。那么 $\mathrm{idom}(u)\rightarrow u$ 的关系形成了一棵树，称其为支配树，记为 $T(S)$ 。显然 $u$ 的支配点都在 $path(S,u)$ 上。我们可以发现， $T(S)$ 上 $S$ 到 $\mathrm{idom}(u)$ 的路径上的所有点就是 $u$ 的所有支配点。这是由于 $\mathrm{idom}(u)$ 是 $u$ 的所有支配点中深度最大的一个，因而其他的 $u$ 的支配点在 dfs 树中都是 $\mathrm{idom}(u)$ 的祖先，所以如果一个 $u$ 的支配点 $v$ 不支配 $\mathrm{idom}(u)$ 的话，就存在一条路径不经过 $v$ 从 $S$ 到 $\mathrm{idom}(u)$ ，而 $\mathrm{idom}(u)$ 到 $u$ 走 dfs 树中的树边也断然不需要经过 $v$ ，这与 $v$ 支配 $u$ 矛盾。结论得证。我们就得到了这个十分优美的结构——支配树。

因此为了求出支配树，我们就需要求出 $\mathrm{idom}(u)$ 。为了求支配点，我们首先观察一个点是如何绕开（ dfs 树的祖先中）那些不支配它的点的。为了方便描述，我们这一段所述的路径实际上是把原图中的边倒过来走的（会特别标注），不过整个图， dfs 树，以及其他东西并没有改变。我们考虑一条由 $u$ 开始，以一个 $path(S,u)$ 上的点 $t$ 作为终点，且不经过 $path(S,u)$ 上的其他点的路径 $l$ （倒着走边），我们希望 $t$ 的深度越小越好（因为至少 $path(t,u)$ 上的点都不支配 $u$ ）。把 $t$ 记为 $\mathrm{sdom}(u)$ 。从 $u$ 出发的第一条边不能是前向边和树边（走到 $path(S,u)$ 上的话路径就直接结束），于是我们走横叉边或后向边。通过横叉边/后向边走到点 $p_1$ 后，我们可以走若干条前向边/树边到达点 $q_1$ （点 $q_1$ 也同样不能在 $path(S,u)$ 上），再走到 $p_2,q_2,\ldots$ 直到某次走到 $path(S,u)$ 上结束。由于这些点都不在 $path(S,u)$ 上，所以 $\forall v\in l,dfn(v)>dfn(u)$ （因为能减小 dfn 的边只有树边和前向边（倒着走），而这两者都只能连接祖先和子孙，不能减到 $dfn(u)$ 以下不然就会碰到 $path(S,u)$）。进一步可以发现，走到 $path(S,q_1)$ 上是没有意义的，不然在 $p_1\rightarrow q_1$ 的时候就可以走过去了，也就是我们把问题规约到了求 $\mathrm{sdom}(q_1)$ 上。最终得到了求 $\mathrm{sdom}(u)$ 的方法：

$$\mathrm{sdom}(u)=\min\{\{v|(v,u)\in E,dfn(v)< dfn(u)\}\cup\{\mathrm{sdom}(q)|dfn(q)>dfn(u),\exists (p,x)\in E,q\in path(S,p)\}\}$$
（第一部分是走树边/前向边，后一部分是递归到 $\mathrm{sdom}(q_1)$ ）

接下来用 $\mathrm{sdom}$ 求 $\mathrm{idom}$ 是相对简单的，由于 $path(\mathrm{sdom}(u),u)$ 上的点都不是支配点了，我们在 上取 $\mathrm{sdom}(v)$ 深度最小的点 $v$ ，从点 $v$ 继续向上爬即可（贪心选 $\mathrm{sdom}(v)$ 最小的点 $v$ 最优可以用归纳法证明），于是：

$$\mathrm{idom}(u)=\begin{cases}\mathrm{sdom}(u) & \mathrm{sdom}(v)=\mathrm{sdom}(u) \\ \mathrm{idom}(v) & \mathrm{sdom}(v) < \mathrm{sdom}(u)\end{cases}$$

支配点/边 强割点/边

上面已经表述了支配点的求法，类似地，我们也可以定义一个点的支配边。

我们可以简单地用支配点来求解支配边。一个支配边 $(u,v)$ 应该满足：只有树边/后向边与 $v$ 相连，且对于所有后向边 $(w,v)$ ， $v$ 支配 $w$ 。证明比较显然。

类似无向图中的概念，我们可以定义有向图中的割点/边。
如果删除一个点/边会使图中的强连通分量数增加，则称其为强割点/边。

我们可以比较容易的看出，求出 $T(S)$ 和 $T^R(S)$ 后，一个强割点/边要么在 $T(S)$ 中是支配点/边，要么在 $T^R(S)$ 中是支配点/边。而反之， $T(S)/T^R(S)$ 中的支配点/边也一定是强割点/边。（注：对于 $S$ 本身需要单独判断是否为强割点）

求解边（强）双连通分量

类似地，我们可以定义有向图中的边双连通性：如果在删除任意一条边后 $u,v$ 仍强连通，则称它们是边双连通的。容易看出边双连通具有传递性，于是一个极大的边双连通子图就称为边双连通分量。

与无向图不同的是，我们不能像无向图一样把割边全部删除。由于有向图的支配性有两个方向，删除一个方向的支配边会对另一个方向产生影响，因此我们有一个自然的想法：先处理 $T(S)$ 再处理 $T^R(S)$ ，在删去支配树 $T$ 中的支配边后，提取出支配树的各个连通分量，对每个连通分量建出新图（保留该连通分量中的所有点，并且使得点之间的连通性（即 $u$ 是否能到达 $v$ ）不变）。由于新图保护了连通性不变，所以再进行下一步也应该是正确的。

建出新图

由于我们对每个连通块都要建出新图，那么怎么在保证复杂度的情况下建出正确的新图呢？

我们按照这样的方法处理：首先把支配树 $T$ 中的每一个连通分量缩成一个点，令新树为 $H$ ，当前我们处理的连通分量为点 $u$ 。在 $H$ 中删掉点 $u$ 会产生 $degree(u)$ 个连通分量，每个连通分量都缩成新图中的一个虚点，连通分量 $u$ 中原有的点称为实点。于是新图中的总点数和是 $O(|H|)$ 的也就是 $O(n)$ 的。
在分析边数的时候我们需要注意到一个事实：新 $G$ 中非树 $H$ 中的边只有后向边（这里的概念是从 dfs 树引申到一般树上的），没有前向边和横叉边（会违背支配性）。而新图中每个虚点只能连向最多一个虚点（也就是 $u$ 的父亲所在的虚点），其余的边都是和实点相连的。因此虚点之间的边总共最多只有 $O(n)$ 条，而和实点相连的边只会被算两次因此总数是 $O(m)$ 的。注意加边的时候是进行去重的。

上面我们证明了，所有连通分量的新图的大小总和是线性的。而建出也比较简单：对于和实点相连的边，直接从实点暴力，对于虚点之间的边，对于图 $G$ 以支配树为生成树类似 dfs 树求出 $low(u)$ 和 $don(u)$ （相当于 $dfn(u)$ ） ，枚举 $u$ 的每个儿子 $v$ ，如果 $low(v)< don(u)$ 那么连一条 $v$ 到父节点的边。

最后我们需要证明，实点 $u,v$ 在新图和原图中的边双连通性是一样的。
考虑点 $u$ 到点 $v$ 的路径，如果路径上所有点都是实点那么显然和原图是一样的；如果经过了 $u$ 的子节点的连通分量的话，就必须要经过一条支配边（支配边定义），在原图和新图中都是一样的；如果经过了父节点的连通分量的话，也必须要经过一条支配边才能回到 $u$ 中。于是得证。

算法描述

def Fast2ECB(G):
    S = 0
    ECB = []
    TS = getDominatorTree(G, S)
    GEdgeDominators = getEdgeDominator(TS)
    Gi = auxiliaryGraphs(TS, GEdgeDominators)
    for s, H in Gi:
        HR = reverseGraph(H)
        TRs = getDominatorTree(HR, s)
        HEdgeDominators = getEdgeDominator(TRs)
        HRi = auxiliaryGraphs(TRs, HEdgeDominators)
        for q, M in HRi:
            M.deleteEdge(M.oldFather(q), q)
            for c in getSCC(M):
                ECB.append(c)
    return ECB

其他的都和我们预想的完全一致：求出 $G$ 的支配树 $T(S)$ ，用支配边把 $T(S)$ 分成若干连通分量（令每个连通分量的根节点为 $s$ ）并建出它们的新图（auxiliary graph） $H$ ，再求出 $H^R$ 的支配树 $T_H^R(s)$ ，再用支配边划分出连通分量（令每个连通分量的根节点为 $q$ ）并建出新图。现在我们需要解释算法的最后一步的删边：
在经过第一步处理到 $H$ 的时候，我们已经能保证在 $T_H(s)$ 中 $s$ 到任何实点的路径上没有强割边，因此如果删掉的边不是 $T_H^R(s)$ 中 $s$ 到 $q$ 路径上的边的话， $u$ 可以到达 $s$ ， $s$ 可以到达 $v$ ，因此 $u,v$ 必然是强连通的。于是删去 $M$ 中 $(q,p)$ 这条边来进行判断就可以了（其他边已经被缩到虚点里去了）。