Description：

给出一张有向图，求其至少需要连多少条边才能强连通，输出方案。

$n,m\leqslant10^6$

Solution：

首先先缩点得到一个 $DAG$ ，如果没有输出方案的话答案就是没有入度的点的个数和没有出度的点的个数的较大值，考虑怎么构造，一个想法是求出最小路径覆盖然后交错着连成一个环，但是网络流显然跑不下，考虑另一种构造，我们可以先求出一组匹配 $(A_1\sim A_r),(B_a\sim B_r)$ ，然后还剩下一些没有入度的点 $(C_1\sim C_p)$ 和没有出度的点 $(D_1\sim D_q)$ ，假设 $q\geqslant 0$ ，那么我们连边： $$ \begin{align} &1、B_1\to A_2,B_2\to A_3,\sim,B_{r-1}\to A_r\\ &2、D_1\to C_1,D_2\to C_2\sim ,D_p\to C_p\\ &3、B_r\to D_{p+1},D_{p+1}\to D_{p+2},D_{p+2}\to D_{p+3},\sim,D_{q}\to A_1 \end{align} $$ 不难发现这样一定是强连通的，而且连边数 $r-1+p+q-p+1=r+q$ 最少。

Code：

没有代码