题目链接：
题意：给出n个学校和一些学校之间的网络链接关系，学校之间的网络是单向边，让你求出两个问题的答案，1.至少需要多少份软件，使得所有学校都可以收到。2.如果希望用一份软件就能够使所有学校收到需要添加几条边
题解：首先求强连通分量然后缩点，所谓缩点就是将一个连通图化为一个点。然后再以联通图构成一个图。
然后这题的问题1只要求联通分量入度为0的点的和就行了，问题2就是求连通分量入度和出度为0的和的最
大值。（为了构成全连通分量构成的图联通，最少要加max（入度为0的，出度为0的）才能保证联通）。
#include#include #include #include using namespace std;const int M = 10000 + 10;const int N = 100 + 10;struct TnT { int v , next;}edge[M];int head[N] , e;int Low[N] , DFN[N] , Stack[N] , Belong[N];int Index , top;int scc;bool Instack[N];int num[N];void init() { memset(head , -1 , sizeof(head)); e = 0;}void add(int u , int v) { edge[e].v = v , edge[e].next = head[u] , head[u] = e++;}void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].v; if(!DFN[v]) { Tarjan(v); Low[u] = min(Low[u] , Low[v]); } else if(Instack[v]) Low[u] = min(Low[u] , DFN[v]); } if(Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++; } while(v != u); }}int In[N] , Out[N];int main() { int n; while(scanf("%d" , &n) != EOF) { init(); for(int i = 1 ; i <= n ; i++) { int x; while(scanf("%d" , &x)) { if(x == 0) break; add(i , x); } } memset(DFN , 0 , sizeof(DFN)); memset(Instack , false , sizeof(Instack)); memset(num , 0 , sizeof(num)); memset(In , 0 , sizeof(In)); memset(Out , 0 , sizeof(Out)); for(int i = 1 ; i <= n ; i++) if(!DFN[i]) Tarjan(i); for(int i = 1 ; i <= n ; i++) { for(int j = head[i] ; j != -1 ; j = edge[j].next) { int v = edge[j].v; if(Belong[i] != Belong[v]) { In[Belong[v]]++; Out[Belong[i]]++; } } } int ans1 = 0 , ans2 = 0; for(int i = 1 ; i <= scc ; i++) { if(In[i] == 0) ans1++; if(Out[i] == 0) ans2++; } if(scc == 1) printf("1\n0\n"); else printf("%d\n%d\n" , ans1 , max(ans1 , ans2)); } return 0;}