题目链接: 

题意：

 给定一个有向图，求：

1) 至少要选几个顶点。才干做到从这些顶点出发，能够到达所有顶点

2) 至少要加多少条边。才干使得从不论什么一个顶点出发，都能到达所有顶点

    顶点数<= 100

求完强连通分量后，缩点，计算每一个点的入度，出度。

 第一问的答案就是入度为零的点的个数，

 第二问就是max(n,m) // 入度为零的个数为n, 出度为零的个数为m. //kuangbin巨巨分析非常棒！

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn = 100 + 10;vector
          
            G[maxn];int dfn[maxn], low[maxn], belong[maxn], dfs_clock, scc_cnt;stack
           
             S;void dfs(int u){ dfn[u] = low[u] = ++dfs_clock; S.push(u); for(int i=0; i
           
          
         
        
       
      
     

3. DAG上面有多少个入度为0的顶点。问题1的答案就是多少 在DAG上要加几条边。才干使得DAG变成强连通的，问题2的答案就是多少 加边的方法： 要为每一个入度为0的点加入入边，为每一个出度为0的点加入出边 假定有 n 个入度为0的点，m个出度为0的点，怎样加边？ 把全部入度为0的点编号 0,1,2,3,4 ....N -1 每次为一个编号为i的入度0点可达的出度0点，加入一条出边，连到编号为(i+1)%N 的那个出度0点, 这须要加n条边 若 m <= n，则 加了这n条边后，已经没有入度0点。则问题解决，一共加了n条边 若 m > n。则还有m-n个入度0点，则从这些点以外任取一点，和这些点都连上边，就可以，这还需加m-n条边。 所以，max(m,n)就是第二个问题的解 此外：当仅仅有一个强连通分支的时候，就是缩点后仅仅有一个点，尽管入度出度为0的都有一个，可是实际上不须要添加清单的项了，所以答案是1。0； */ /* input: 30 18 0 7 21 0 1 4 15 28 0 9 0 10 15 16 0 22 26 0 1 5 10 12 0 3 17 29 0 2 5 17 0 19 23 0 20 0 1 7 15 19 0 0 23 0 0 0 5 18 0 0 7 18 0 17 0 24 0 13 21 0 26 0 0 2 23 30 0 2 9 11 13 14 27 0 2 0 14 0 0 28 0 output: 3 6 */