POJ-1236 Network of Schools

Network of School
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

 

---

 

解题思路

Subtask A 即为求解在图G中，至少要选择几个节点，才能沿这些节点出发遍历完整个网络。
Subtask B 即为需要在图G中，添加多少条边，使从任何一个节点出发，都能遍历完整个网络。

做法
1.使用tarjan算法求强连通分量(SCC)进行缩点
2.统计入度为0的点的个数n和出度为0的点的个数m
3.Subtask A的解为n    Subtask B的解为max(m,n)

 

---

全局变量
[cc lang=”C++”]
vector map[MAXN]; //储存图

int dfn[MAXN];
int low[MAXN];
int time_stamp;

int sccNo[MAXN];
int scc_cnt;

int in[MAXN]; //储存出度
int out[MAXN]; //储存入度

int n;

stack <int> Point;

[/cc]

 

Tarjan算法求强联通分量
[cc lang=”C++”]
void tarjan(int index){
dfn[index] = low[index] = ++time_stamp;

    Point.push(index);

    for(int i=0;i<map[index].size();i++){
        int v = map[index][i];

        if(!dfn[v]){
            tarjan(v);
            low[index] = min(low[index],low[v]);
        }else if(!sccNo[v])
            low[index] = min(low[index],dfn[v]);
    }

    if(dfn[index] == low[index]){
        scc_cnt++;

        while(true){
            int tmp = Point.top();
            Point.pop();

            sccNo[tmp] = scc_cnt;

            if(tmp == index)
                break;
        }
    }
}

[/cc]

 

solve函数
[cc lang=”C++”]
void solve(){
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);

            //如果只有1个强联通分量，特判
    if(scc_cnt==1){
        printf("1\n0\n");
        return;
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<map[i].size();j++){
            int v= map[i][j];

            if(sccNo[i] != sccNo[v]){
                                    //缩点，两个端点不在同一强联通分量才处理
                in[sccNo[v]]++;
                out[sccNo[i]]++;
            }
        }
    }

    int ans1=0; //多少个入度为0的节点
    int ans2=0; //多少个出度为0的节点

    for(int i=1;i<=scc_cnt;i++){
        if(!in[i])
            ans1++;
        if(!out[i])
            ans2++;
    }

    printf("%d\n%d\n",ans1,max(ans1,ans2));
}

[/cc]