Problem

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

Solution

先对 $G$ 求强连通分量，用 tarjan 算法即可。缩点，然后得到一个 DAG。如果最后的 DAG 只有一个节点，那么答案是 0 ，否则答案是 $max(indegree, outdegree)$，$indegree$ 和 $outdegree$ 分别表示入度为 0 的点的总数和出度为 0 的点的总数。

Proof

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

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

First: $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$。