题目链接：

 

题意是告诉你有n个命题，m条递推关系，表示某个命题可以推出另外一个命题。

现在问你至少在增加多少个递推关系可以保证所有命题两两互推。

 

把命题看成一个结点，推导看成有向边，就是n个结点，m 条有向边，要求添加尽量少的边，使得新图强连通。

 

首先找出强连通分量，把每个强连通分量缩成一个点，得到DAG。设有 a 个结点入度为 0 ，b 个结点出度为 0 ，max(a,b)，就是答案。如下图：

 

入度为 0 的集合 为 1，出度为 0 的集合 为 2，要加两条红边才能 互相到达（强连通）。

先标记所有强连通图的入度出度 1 ，要是有点相同，标记为 0 ，统计 入度为 1 ，出度为 1 的个数。

如果原图只有一个强连通分量 ans = 0 不需要加边。

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