[POJ 1236] Network of Schools 题解

题目翻译：

有一些学校被网络连接，学校之间签了协议：每一个学校维护一个它所要提供软件的学校的名单。注意如果A出现的B学校的名单中，B不一定出现在A学校名单中。你被要求写一个程序来计算最少需要多少个学校接受到新软件可以让软件按照协议被提供给所有的学校（A任务）。作为进一步的任务，我们想确保把软件送给任意一个学校能够使所有学校都获得软件，我们可以通过在两个学校之间添加新的连接来达到这个任务。计算最少需要添加多少新的连接（B任务）。

题解：

　　把学校看作节点，在每个学校和它需要提供软件的学校之间连接一条有向边，整个关系就构成了一张有向图，我们可以用Tarjan算法求出有向图中的所有强连通分量，那么每一个强连通分量中的学校能互相提供软件，然后进行缩点，把每个强连通分量看作一个节点，那么原有向图就构成了一张新的有向无环图，任务A的答案就是那些入度为0的节点个数，因为入度为0的节点不能被任何其他节点提供软件。任务B的答案就是$max{$入度为0的节点个数，出度为0的节点个数$}$，我们所要做的是在入度为0的节点和出度为0的节点加边。注意若整张图本身就是一个强连通分量，那么任务B答案为0。

附上代码：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=120;
int dfn[N],low[N],stac[N],ins[N],c[N],in[N],out[N];
vector<int> son[N];
int n,cnt,top,tot,p,q;

void Tarjan(int x){
    dfn[x]=low[x]=++cnt;
    stac[++top]=x,ins[x]=1;
    for(int i=0;i<son[x].size();++i){
        int y=son[x][i];
        if(!dfn[y]){
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(ins[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        tot++;int y;
        do{
            y=stac[top--],ins[y]=0;
            c[y]=tot;
        }while(x!=y);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1,x;i<=n;++i) while(scanf("%d",&x) && x) son[i].push_back(x);
    for(int i=1;i<=n;++i) if(!dfn[i]) Tarjan(i);
    for(int x=1;x<=n;++x){
        for(int i=0;i<son[x].size();++i){
            int y=son[x][i];
            if(c[x]!=c[y]){
                in[c[y]]++,out[c[x]]++;
            }
        }
    }
    for(int i=1;i<=tot;++i){//统计入度为0和出度为0的节点个数
        if(!in[i]) p++;
        if(!out[i]) q++;
    }
    if(tot==1){
        printf("1\n0\n");
    }else printf("%d\n%d",p,max(p,q));
    return 0;
}