学校网络 - 凌冬的个人博客

一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校 A 支援学校 B，并不表示学校 B 一定要支援学校 A）。

当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。

因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。

现在请问最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？

最少需要添加几条新的支援关系，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

输入格式

第 1 行包含整数 N ，表示学校数量。

第 2..N+1 行，每行包含一个或多个整数，第 i+1 行表示学校 i 应该支援的学校名单，每行最后都有一个 0 表示名单结束（只有一个 0 即表示该学校没有需要支援的学校）。

输出格式

输出两个问题的结果，每个结果占一行。

数据范围

$ 2≤N≤100 $

输入样例：

输出样例：

解题思路

证明所有起点都无法由别的点到达，因此每个起点必须分配一个软件，而对于其他所有点，一定存在前驱，一定能由某一个起点走到，也就是说从所有起点出发，能遍历整个图。因此只需要给所有起点各一个软件即可。

Tarjan缩点将原图转化成 DAG ，统计每个强连通分量的出度入度，起点数量为 src，终点数量为 des 。对于一个强连通分量，其中只要有一所学校获得新软件那么整个分量都能获得。

首先，可以进行缩点.
子任务1：缩点后入度为零的强连通分量必须要有新软件.
子任务2：要求加边后形成一个强连通图。可以考虑到缩点后的DAG上每个点都必须同时具有入度和出度，就可以将没有入度的点的数量记为p，没有出度的点的数量记为q；由于没有出度的点可以直接连接没有入度的点，答案即为max(p,q).
正确性显然.

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82


#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150;
int dfn[MAXN] , low[MAXN] , flag;

unordered_map<int,vector<int> > path;

int stk[MAXN], in_stk[MAXN] , top;
int din[MAXN] , dout[MAXN];
int scc_cnt;
int scc_size[MAXN], id[MAXN];
int n,m;
void tarjan(int u) 
{
    low[u] = dfn[u] = ++flag;
    stk[++top] = u, in_stk[u] = 1;
    for(int next: path[u]) {
        if(! dfn[next] ) {
            tarjan(next);
            low[u] = min(low[u] , low[next]);
        }else if(in_stk[next]) {
            low[u] = min(low[u] , dfn[next]);
        }
    }
    
    if(low[u] == dfn[u]) {
       int y = -1;
       ++scc_cnt;
       do {
           y = stk[top--];
           in_stk[y] = false;
           id[y] = scc_cnt;
       }while(y != u && top>0);
    }
    
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) {
        int t;
        while(cin>>t,t) path[i].push_back(t);
    }
    
    
    for(int i=1;i<=n;++i) 
        if(!dfn[i]) 
            tarjan(i);
    
    for(int i=1;i<=n;++i) {
        for(int v: path[i]) {
            int x = id[i] , y = id[v];
            // printf("x,y %d %d\n",x,y);
            if(x!=y) {
                //不在一个联通分量里面
                dout[x]++;
                din[y]++;
                // printf("%d %d\n",x,y);
            }
        }
    }
    
    int a = 0
    ,b = 0;
    for(int i=1;i<=scc_cnt;++i) {
        // printf("din:=%d \n",din[i]);
        if(!din[i]) a++;
        if(!dout[i]) b++;
    }
    
    printf("%d\n",a);
    // printf("scc_cnt := %d\n",scc_cnt);
    if(scc_cnt == 1) puts("0");
    else printf("%d\n",max(a,b));
    
    
    
    
    
    return 0;
}

文章目录