Language:
Network of Schools
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 30208Accepted: 11857

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

Source

IOI 1996

题意：略；
思路：tarjan算法缩点，重点在求解，在tarjan算法将图改为DAG后，注意我们把入度为0的点称为起点，相应的我们把出度为0的点称为终点。第一问询问至少需要几个学校，答案是起点的数量，因为由一个起点能遍历到某些点，但永远不可能遍历到另外一个起点，所以起点的数量就是第一问的答案；
第二问询问至少需要添几条边，将有向图变成强连通图，不妨还是站在起点终点的角度去考虑，我们要变成强连通图，必须保证消灭所有的起点和终点，因为一个点若是起点，那么除自身外任何一个点均到达不了他，一个点若是终点，那么他到达不了任何点，所以应在图中终点连起点，答案就是max(起点数量，终点数量)，需要注意的是存在一种状态，即图本身便是强连通图，即它本身既是起点又是终点，显然情况ans为0；

代码如下：


#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#define pb push_back
using namespace std;
const int N = 1e4+10,M=2e5+10;
int n,var[M],head[N],nxt[N],tot,t,cnt,id[N],all[N],dfn[N],low[N];bool st[N];
void add(int x,int y){
    var[++tot] = y,nxt[tot] = head[x],head[x] = tot;
}
vector<int>s[N];
stack<int>G;
void tarjan(int x){
    low[x] = dfn[x] = ++t;
    st[x] = true;G.push(x);
    for(int i=head[x];i;i=nxt[i]){
        int y = var[i];
        if(!dfn[y]){
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }
        else if(st[y] == true)low[x] = min(low[x],dfn[y]);
    }
    if(dfn[x] == low[x]){
        int k;++cnt;
        do{
            k = G.top();
            st[k] = false;
            G.pop();
            id[k] = cnt;all[cnt]++;
        }while(k!=x);
    }
}
int in[N],out[N];bool vis[N];int x;
void solve(){
    scanf("%d",&n);
    //tot = 1;
    for(int i=1;i<=n;++i)while(true){
        int v;
        scanf("%d",&v);
        if(v == 0)break;
       //if(v == i)continue;
        add(i,v);
    }
    for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i){
        for(int y=head[i];y;y=nxt[y]){
            int p = var[y];
            if(id[p]!=id[i]){
                in[id[p]]++;out[id[i]]++;
                //s[id[i]].pb(id[p]);
            }
        }
    }
    int ans2 = 0,ans1 = 0;
    for(int i=1;i<=cnt;++i){
        if(in[i] == 0){
            ans1++;
        }
        if(out[i] == 0)ans2++;
    }
    if(cnt == 1)ans2 = 0;
    else ans2 = max(ans1,ans2);
    printf("%d\n%d\n",ans1,ans2);
}

int main(){
    solve();
    return 0;
}

写在最后，感觉这个将图补成强连通图的问题可以当做一个结论，结论就是max(入度为0的点，出度为0的点)，有些许的偏思维；

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章