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$.