添加最少的边让有向图强连通

Problem

给定一个有向图 $G$ ，问至少添加几条有向边可以使得 $G$ 强连通。

Solution

先对 $G$ 求强连通分支，缩点，然后得到一个DAG。如果最后的DAG只有一个节点，那么答案是0，否则答案是 $\max(in, out)$ ，这里 $in$ 和 $out$ 分别表示入度为0的点的总数和出度为0的点的总数。

Proof

首先 $\max(in, out)$ 肯定是一个下界，因为至少需要这么多边才能完全消除入度为0的所有的点或者出度为0的所有的点。

接着，我们用归纳法来构造一组合理的解。给定任意一个图 $G$ ，求它的强连通分量并且缩点得到一个DAG，令这个DAG为 $D$ 。我们假设 $|D| \ge 2$ ，否则答案很显然是0。令 $X$ 和 $Y$ 分别表示 $D$ 中入度和出度为0的点集。令 $m = \max(|X|, |Y|)$ 。我们通过对 $m$ 进行归纳，claim是存在一种添加 $m$ 条边的解法让 $G$ 变得强连通。

Base: $m = 1$

这个时候，很显然我们有 $|X| = |Y| = 1$ 。假设 $x$ 和 $y$ 分别是 $X$ 和 $Y$ 的唯一元素，那么我们只需要添加边 $(y, x)$ 即可。

当 $m \ge 2$ 的时候，我们考虑2个case。

Case 1:

存在 $x \in X$ , $y \in Y$ 使得 $D$ 不存在从 $x$ 到 $y$ 的路径。这时我们添加一条边 $(y, x)$ 。假设添加过边的新图为 $G’$ ，求它的强连通分支并且缩点得到一个DAG $D’$ 。我们可以断定 $D’ = D \cup {(y, x)}$ 。原因很简单，如果 $D$ 的点集在添加边 $(y, x)$ 后发生了变化，唯一的可能是边 $(y, x)$ 构成了环，这说明我们有 $x$ 到 $y$ 的路径，矛盾。

现在考虑新图 $G’$ 和它的DAG $D’$ ，与 $D$ 相比， $D’$ 少了一个入度为0的点，也少了一个出度为0的点，所以 $m’ = m - 1$ 。根据归纳假设，我们需要再递归地添加 $m’ - 1$ 条边，加上 $(y, x)$ 本身，一共 $m$ 条。

Case 2:

不存在上述的 $x$ 和 $y$ ，这意味着在DAG $D$ 中所有的 $x \in X$ 都有到所有的 $y \in Y$ 通路。这时我们可以随意取 $D$ 中出度为0的点 $y$ 和入度为0的点 $x$ ，添加边 $(y, x)$ 。如此重复 $m$ 次即可。需要注意的是，如果某个时候不存在出度为0的点，那么就在 $Y$ 中任取一点，如果不存在入度为0的点，就在 $X$ 中任取一点。一个合理的推论是，当上述操作完成后，我们有以下两个性质：

i. 对于 $X$ 中的任何一点 $x$ ，存在某个 $y \in Y$ 使得我们有边 $(y, x)$ 。

ii. 对于 $Y$ 中的任何一点 $y$ ，存在某个 $x \in X$ 使得我们有变 $(y, x)$ 。

接下来，我们需要证明，为什么这样随意的添加边之后 $D$ 会变得强连通（因此 $G$ 也就强连通了）。实际上，任取 $D$ 中的两个点 $a$ 和 $b$ ，首先一定存在某个 $y_1 \in Y$ （ $y_1$ 可能是 $a$ 本身），使得有 $a$ 到 $y_1$ 的路径。其次，根据性质(ii)，存在某个 $x_1 \in X$ 使得我们有边 $(y_1, x_1)$ 。再看点 $b$ ，容易知道一定存在某个 $x_2 \in X$ 使得 $D$ 中存在 $x_2$ 到 $b$ 的路径( $x_2$ 可能是 $b$ 本身)。再根据性质(i)，存在某个 $y_2 \in Y$ 使得我们有边 $(y_2, x_2)$ 。最后，根据一开始的假设， $X$ 中的每个点都有到 $Y$ 中每个点的路径，即存在 $x_1$ 到 $y_2$ 的路径，于是我们找到了一条通路 $a \rightsquigarrow y_1 \rightarrow x_1 \rightsquigarrow y_2 \rightarrow x_2 \rightsquigarrow b$ .