。

题意：

至少增加几条边，才能让图强连通。

分析：

“首先，找出强连通分量，然后把每个强连通分量缩成一个点（缩点），得到一个DAG。 接下来，设有a个结点的入读为0， b个结点的出度为0， 则 max{a, b}就是答案。 注意特殊情况： 当原图已经强连通时， 答案是0而不是1."

这是《算法竞赛入门经典——训练指南》上的原话。对于证明，搜了一下，没有找到。自己呢，试着画了一下，记下个人心得。

自己的理解如下；一个含n个点的图，至少要有n条边，才能强连通。即每一个点至少都会有一个入度和出度。对于得到的DAG，设有a个结点的入度为0， b个结点的出度为0，因为增加一条边会同时增加一个入度和一个出度，因此要强连通，即，要想消去所有入度或出度为0的点，至少要 max{a,b}条边。

对于所述的特殊情况， 当原图已经强连通时，缩点后，整个图会成为一个点，max{a,b} = 1, 但这并不正确，因为本身整个图就强连通，需要0条边。

AC代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 20000+10;vector
            
              G[maxn];stack
             
               S;int pre[maxn], lowlink[maxn], scc_cnt, sccno[maxn], dfs_clock;int in0[maxn], out0[maxn];void dfs(int u){ pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for(int i=0; i