题目链接：http://poj.org/problem?id=1236

题意：给出n个学校和一些学校之间的网络链接关系，学校之间的网络是单向边，让你求出两个问题的答案，1.至少需要多少份软件，使得所有学校都可以收到。2.如果希望用一份软件就能够使所有学校收到需要添加几条边

题解：首先求强连通分量然后缩点，所谓缩点就是将一个连通图化为一个点。然后再以联通图构成一个图。

然后这题的问题1只要求联通分量入度为0的点的和就行了，问题2就是求连通分量入度和出度为0的和的最

大值。（为了构成全连通分量构成的图联通，最少要加max（入度为0的，出度为0的）才能保证联通）。

#include <iostream>#include <cstring>#include <vector>#include <cstdio>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;}

poj 1236 Network of Schools（tarjan缩点）