POJ-1236 Network of Schools （強連通分量[Tarjan]）

Network of Schools http://poj.org/problem?id=1236

Time Limit: 1000MS	Memory Limit: 10000K

Description

A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B 

You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school. 

Input

The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

Output

Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

Sample Input

5
2 4 3 0
4 5 0
0
0
1 0
      

Sample Output

1
2      

題目大意：給定一個有向圖，求： ① 至少要選幾個頂點，才能做到從這些頂點出發，可以到達全部頂點  ② 至少要加多少條邊，才能使得從任何一個頂點出發，都能到達全部頂點

首先又得了解到一個定理：有向無環圖中所有入度不為0的點，一定可以由某個入度為0的點出發可達。（由于無環，是以從任何入度不為0的點往回走，必然終止于一個入度為0的點）

則可以處理出所有的強連通分量，并将強連通分量縮成一點，新圖中入度為0的點數即為第①問答案

若要新圖成為一個強連通分量，則不存在出度或入度為0的點，則兩者中的較大值為第②問答案

注意：如果新圖隻有一個強連通分量，則第②問答案為0

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN=105;

int n,s,e,num,cnt;//num表示時間戳，cnt表示強連通分量個數
int stak[MAXN],top;//top指向棧頂元素的後一個，也表示棧内元素個數
int dfn[MAXN],low[MAXN],color[MAXN],indeg[MAXN],outdeg[MAXN];
vector<int> edge[MAXN];
bool isIn[MAXN];

void Tarjan(int u) {
    dfn[u]=low[u]=++num;
    isIn[u]=true;//标記點u在棧中
    stak[top++]=u;//目前點入棧
    int v;
    for(int i=0;i<edge[u].size();++i) {
        v=edge[u][i];
        if(dfn[v]==0) {//如果點v未周遊
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(isIn[v]&&dfn[v]<low[u]) {//如果點v已周遊且在棧中
            low[u]=dfn[v];
        }
    }
    if(dfn[u]==low[u]) {
        ++cnt;//強連通分量數+1
        do {
            v=stak[--top];
            isIn[v]=false;//标記點v不在棧中
            color[v]=cnt;//強連通分量縮成一點
        } while(u!=v);
    }
}

void solve() {
    num=cnt=top=0;
    memset(dfn,0,sizeof(dfn));
    memset(isIn,false,sizeof(isIn));
    for(int i=1;i<=n;++i)
        if(dfn[i]==0)
            Tarjan(i);

    memset(indeg,0,sizeof(indeg));
    memset(outdeg,0,sizeof(outdeg));
    for(int i=1;i<=n;++i) {
        for(int j=0;j<edge[i].size();++j) {
            if(color[i]!=color[edge[i][j]]) {//如果不在一個縮點中，則更新各自縮點的出入度
                ++outdeg[color[i]];
                ++indeg[color[edge[i][j]]];
            }
        }
    }
    int cntIn=0,cntOut=0;//cntIn表示入度為0的縮點個數；cntOut表示出度為0的縮點個數
    for(int i=1;i<=cnt;++i) {
        if(indeg[i]==0)
            ++cntIn;
        if(outdeg[i]==0)
            ++cntOut;
    }
    printf("%d\n%d\n",cntIn,cnt==1?0:max(cntIn,cntOut));//注意如果隻有一個強連通分量（包括n==1），則不需要添加邊
}

int main() {
    while(scanf("%d",&n)==1) {
        for(int i=1;i<=n;++i)
            edge[i].clear();
        for(int i=1;i<=n;++i) {
            scanf("%d",&e);
            while(e!=0) {
                edge[i].push_back(e);
                scanf("%d",&e);
            }
        }
        solve();
    }
    return 0;
}