题目链接：https://vjudge.net/problem/POJ-1236

题目：有向图，有若干个连通图，点之间有单向边边就可以单向传递信息，问：

（1）至少需要发送几份信息才能使得每个点都传递到信息

（2）至少需要加几条边，才能使得“把一份信息发送到任意某个点就能传播到其他所有点”成立

思路：tarjan求强连通分量，强联通分量可以相互传递消息，然后，按强联通编号重构图，

统计每个强联通分量的入度出度情况。第一个答案，就显然是入度为0的点，第二个就是max(p,q)，构成一个强联通图

这里给情况来解释下max    （1）1->2   3->2     （2） 1->2   1->3

p = 入度为0的强联通分量数

q = 出为为0的强联通分量数

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5  6 const int N = 110; 7 int head[N],dfn[N],low[N],scc_no[N],s[N],ins[N],ru[N],chu[N]; 8 int n,scc,tim,tot,top; 9 struct node{10 int to;11 int nxt;12 }e[N*N];13 14 inline void add(int u,int v){15 e[tot].to = v;16 e[tot].nxt = head[u];17 head[u] = tot++;18 }19 20 void tarjan(int now,int pre){21 dfn[now] = low[now] = ++tim;22 ins[now] = 1;23 s[top++] = now;24 25 int to;26 for(int o = head[now]; ~o; o = e[o].nxt){27 to = e[o].to;28 if(!dfn[to]){29  tarjan(to,now);30 low[now] = min(low[now],low[to]);31  }32 else if(ins[to] && low[now] > dfn[to]) low[now] = dfn[to];33  }34 35 if(dfn[now] == low[now]){36 int x;37 ++scc;38 do{39 x= s[--top];40 ins[x] = 0;41 scc_no[x] = scc;42 }while(now != x);43  }44 }45 46 //重构图，统计入度出度情况47 void rebuild(){48 int to;49 for(int now = 1; now <= n; ++now){50 for(int o = head[now]; ~o; o = e[o].nxt){51 to = e[o].to;52 if(scc_no[to] != scc_no[now]){53 ++ru[scc_no[to]];54 ++chu[scc_no[now]];55  }56  }57  }58 }59 60 int main(){61 62 scanf("%d",&n);63 for(int i = 0; i <= n; ++i) head[i] = -1;64 int v;65 for(int u = 1; u <= n; ++u){66 while(~scanf("%d",&v) && v){67  add(u,v);68  }69  }70 for(int i = 1; i <= n; ++i){71 if(!dfn[i])72  tarjan(i,i);73  }74  rebuild();75 int p = 0,q = 0;76 for(int i = 1; i <= scc; ++i){77 if(!ru[i]) ++p;78 if(!chu[i]) ++q;79  }80 if(scc == 1) printf("1\n0\n");81 else printf("%d\n%d\n",p,max(p,q));82 83 84 return 0;85 }