1515：网络协议

【题目描述】

出自 IOI 1996

一些学校连接在一个计算机网络上。学校之间存在软件支援协议。每个学校都有它应支援的学校名单（学校 a 支援学校 b，并不表示学校 b 一定支援学校 a）。当某校获得一个新软件时，无论是直接得到还是网络得到，该校都应立即将这个软件通过网络传送给它应支援的学校。因此，一个新软件若想让所有连接在网络上的学校都能使用，只需将其提供给一些学校即可。

任务

请编一个程序，根据学校间支援协议（各个学校的支援名单），计算最少需要将一个新软件直接提供给多少个学校，才能使软件通过网络被传送到所有学校；

如果允许在原有支援协议上添加新的支援关系。则总可以形成一个新的协议，使得此时只需将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件。编程计算最少需要添加几条新的支援关系。
【输入】

第一行是一个正整数 n
，表示与网络连接的学校总数。随后 n 行分别表示每个学校要支援的学校，即：i+1 行表示第 i 号学校要支援的所有学校代号，最后 0

结束。

如果一个学校不支援任何其他学校，相应行则会有一个 0

。一行中若有多个数字，数字之间以一个空格分隔。
【输出】

包含两行，第一行是一个正整数，表示任务 a
的解，第二行也是一个正整数，表示任务 b

的解。
【输入样例】

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

【输出样例】

1
2

【提示】

数据范围与提示:

2≤n≤100
。

任务 a ：对于每个入度为0的点，没有学校为它提供软件，需要给它提供软件。
任务 b ：统计出度与入度为0的点的个数，出度为0（孤立点，每一条路径末端边缘点）入度为0（孤立点，每一条路径首端边缘点）。两者求最大值

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int e[N], w[N], ne[N], h[N], idx;
int n, m;
int stk[N], in_stk[N], top;
int dfn[N], low[N], timestamp;
int id[N], scc_cnt;
int din[N], dout[N];


void add(int a,int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}


void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = 1;
    
    for(int i = h[u]; ~i ; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j])
        {
            low[u] = min(low[u], dfn[j]);
        }
    }
    
    if(dfn[u] == low[u])
    {
            ++scc_cnt;
            int y;
            do
            {
                y = stk[top--];
                in_stk[y] = 0;
                id[y] = scc_cnt;
            }while(y != u);
    }
    
}

int main()
{
    scanf("%d",&n);
    memset(h, -1, sizeof(h));
    for(int i = 1 ; i <= n ; i++)
    {
        int x;
        while(~scanf("%d",&x))
        {
            if(x == 0) break;
            add(i, x);
        }
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = h[i] ; ~j ; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if(a != b)
            {
                dout[a]++;
                din[b]++;
            }
        }
    }
    
    int a = 0, b = 0;
    for(int i = 1; i <= scc_cnt; i++)
    {
        if(!din[i]) a++;
        if(!dout[i]) b++;
    }
    
    printf("%d\n",a);
    if(scc_cnt == 1) printf("0");
    else printf("%d",max(a, b));
    return 0;
}

1515：网络协议

推荐阅读