「Network of Schools」学校网络

GitHub跳转原题关系图返回列表

求 SCC 并缩点成 DAG：第一问的答案是入度为 0 的分量数，第二问在分量数大于 1 时是入度 0 与出度 0 分量数的较大值，只有一个分量时为 0。

OJ: roj

题目 ID: 3197

难度:提高

标签:图论强连通分量缩点Kosarajupython

创建: 2026-10-02 01:09

更新: 2026-10-10 13:00

前置题目

shumeng CSP201509D高速公路B 直接复用 A 教的「互相可达 ⟺ 同属一个强连通分量、可缩点成 DAG」这一步：A 据此按分量大小累加 C(s,2) 算城市对，B 则在同一缩点 DAG 上统计源分量数 S 与汇分量数 T，再叠加 max(S,T) 加边构造与单分量特判，主要难度在度数结论而不在 SCC 本身。luogu P3387【模板】缩点缩点模板题，先掌握如何把强连通分量缩成一个点、在原图和反图上各跑一遍 DFS，再来看本题的度数结论。

后置题目

luogu P5676[GZOI2017] 小z玩游戏A 教的关键观察「互相可达的点合并为同一强连通分量（SCC），同分量内点可整体处理」被 B 直接用作判定条件：B 把兴奋值当状态建值图后，游戏 i 能玩两次当且仅当 e_i 与某个整除 w_i 的值 x 同 SCC（main.cpp 的 scc_id[div_nodes[j]] == my_scc；brute.cpp 亦沿用 A 的两遍 Kosaraju 缩点判非平凡分量），B 额外叠加的只是「后续可选游戏只取决于当前兴奋值」的值图建模与约数枚举这一层。luogu P1653[USACO04DEC] Cow Ski Area GA 详细证明的「缩点 DAG 中每个源分量要补入边、每个汇分量要补出边，一条边只能同时补一对，故 answer=max(源,汇)，单分量特判 0」这一具体结论被 B 原样用作最后一步：B 的 main.cpp 同样用 indeg/outdeg 标记加 max(source_cnt, sink_cnt)，并保留 comp_cnt==1 输出 0 的特判，B 额外叠加的只是网格建模与「同高连通块即 SCC」的观察；B 的 brute.cpp 还直接沿用 A 的 Kosaraju 缩点度数流程。HDU 3639Hawk-and-ChickenB 的 Tarjan 缩点后用 dag_indeg[su]++ 统计出度、再以 dag_indeg[i]==0 判定原图汇点，正是 A 教的那一步：缩点后每个汇分量（SCC）都没有出边；B 把它用作反向 DAG 的入度为 0 起点（'只有入度为0的点（原图的汇点）才可能是最终赢家'）再叠加从这些分量 DFS 求点权和。

相似题目

roj 1515「一本通 3.5 练习 1」网络协议同模型同公式：两问都是源分量数与 max(源分量数, 汇分量数)，可以直接对照实现。luogu P2746[IOI 1996 / USACO5.3] 校园网 Network of Schools同源题目（IOI 1996 校园网 / Network of Schools），问题设置与答案公式完全一致。

形式化题目

给定有向图 $G = (V, E)$ ， $|V| = n$ 。一条边 $A \to B$ 表示学校 $A$ 会把软件传给学校 $B$ ，且传播会沿边一直继续。

求最少的起点集合 $S \subseteq V$ ，使得从 $S$ 中每个点出发的可达点并集等于 $V$ ；
求最少添加多少条有向边，使得加边后的图任意两点互相可达（强连通）。

样例的图是 $1 \to 2,\ 1 \to 4,\ 1 \to 3,\ 2 \to 4,\ 2 \to 5,\ 5 \to 1$ ：其中 $\{1, 2, 5\}$ 互相可达，另外 $3, 4$ 各自单独成一块。下面的图展示缩点后的结构。

flowchart LR
  A["SCC A: 1 2 5"] --> B["SCC B: 3"]
  A --> C["SCC C: 4"]

图中只有 $A$ 没有入边，所以至少要给它一个软件（第一问答案 $1$ ）； $B$ 和 $C$ 都没有出边，要把它们接进环里至少各需要一条新边。源分量只有 $1$ 个、汇分量有 $2$ 个，取较大值得到第二问答案 $2$ 。

正解

思路

朴素想法

第一问可以直接枚举起点集合，逐个检查能否覆盖全部点；第二问可以枚举要添加的边集合，每加一次就跑一遍强连通判定。第一问要试 $2^{n}$ 个集合，第二问的候选边更多、枚举量更大， $n = 100$ 时都完全不可行。

但本题真正值得利用的性质不是"枚举得太慢"，而是结构本身很规整：传播关系是传递的，"互相可达"这一关系把点天然划成了等价类。

关键观察：缩点后只剩度数

把"互相可达"的点合并成一个强连通分量（SCC），就得到一张 DAG——分量之间不可能再互相可达，否则它们就该被合并。同一个分量内的点，要么全部收到软件，要么全部收不到，因此两个问题都只需要在缩点后的 DAG 上回答。

设缩点后有 $S$ 个入度为 0 的分量（源分量，没有任何分量指向它）， $T$ 个出度为 0 的分量（汇分量）。

第一问的答案是 $S$ 。

每个源分量都没有入边，外部任何点都到不了它，所以每个源分量都必须自己提供一个起点，起点数 $\geqslant S$ ；
反过来，取每个源分量里任意一点作为起点，DAG 上任意分量 $D$ 沿反向边一直往回退，由于 DAG 无环必然停在某个入度为 0 的分量上，把这条路径反向就是源分量到 $D$ 的一条路径，于是 $D$ 也被覆盖。起点数 $\leqslant S$ 。

两边夹起来，答案就是 $S$ 。

第二问的答案是：只有一个分量时为 $0$ ，否则 $\max(S, T)$ 。

下界：加边后图强连通，则每个源分量必须获得至少一条新的入边（它原本一条入边都没有），每个汇分量必须获得至少一条新的出边。而一条新边只能给一个源分量补入度、同时给一个汇分量补出度，所以加边数 $\geqslant \max(S, T)$ 。
上界（可以构造出来）：把 $S$ 个源分量和 $T$ 个汇分量首尾配对连成环——给每个源分量牵一条来自某个汇分量的入边，给每个汇分量牵一条通往某个源分量的出边，多余的配额挂到已经连好的分量上，总共 $\max(S, T)$ 条边。环一旦形成，环上任意两点互相可达；而任何其它分量都能从某个源分量走到、也能走到某个汇分量，因此也被卷进环里，全图强连通。
特判：全图本身只有一个 SCC 时 $S = T = 1$ ，但此时不需要加任何边，答案是 $0$ 。所以必须先判"分量个数是否为 1"，不能只看 $S = T = 1$ 。反例：一条 $1 \to 2 \to \dots \to n$ 的链， $S = T = 1$ 却需要补 $1$ 条边（本题真实数据 input-1 就是这个形状）。

样例对照

样例缩点后只有一个源分量 $A$ 、两个汇分量 $B, C$ ，对应答案 $1$ 和 $\max(1,2) = 2$ 。

分量	包含的点	跨分量出边	跨分量入边	是源？	是汇？
$A$	$1, 2, 5$	$A \to B$ 、 $A \to C$	无	是	否
$B$	$3$	无	$A \to B$	否	是
$C$	$4$	无	$A \to C$	否	是

表格逐行给出每个分量是否含有跨分量的入边/出边：只有 $A$ 是源、 $B$ 与 $C$ 是汇，于是 $S = 1$ 、 $T = 2$ 。分量内部的边（例如 $1 \to 2$ 、 $2 \to 5$ 、 $5 \to 1$ ）不出现在两列里——缩点后它们变成分量里的自环，对度数统计没有影响。

实现：Kosaraju 两遍 DFS

求 SCC 用 Kosaraju：

在原图上 DFS，记录每个点的完成时间（出边全部走完的时刻）；
按完成时间从晚到早的顺序，在反图上再 DFS，每次 DFS 访问到的点集就是一个强连通分量。

直觉是：完成时间最晚的点一定属于某个"源头侧"的分量，在反图上从它出发只能走回它自己所在的分量内部。

代码里两遍 DFS 都写成迭代式：栈元素是 (点, 下一条待走出去的边的下标)，当边的下标走到尽头时弹出该点，就等价于递归版的"函数返回"。这样既不依赖 sys.setrecursionlimit，也避免了深链上的递归风险。分量编号直接取该分量第二遍 DFS 的起点（完成时间最晚的那个点），不同分量的起点互不相同，所以编号天然唯一。

代码

cpp

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 学校网络：Kosaraju 求强连通分量，缩点后数入度 / 出度为 0 的分量
#include <cstdio>
#include <vector>
using namespace std;

int n;
vector<vector<int> > g, rg;

// 第一遍 DFS（迭代版）：返回按完成时间从早到晚排列的点
void finish_order(vector<int>& order) {
    vector<char> seen(n, 0);
    for (int root = 0; root < n; root++) {
        if (seen[root]) {
            continue;
        }
        seen[root] = 1;
        vector<int> sv, si; // 显式栈：(点, 下一条待走出去的边的下标)
        sv.push_back(root);
        si.push_back(0);
        while (!sv.empty()) {
            int v = sv.back();
            int i = si.back();
            if (i == (int)g[v].size()) {
                order.push_back(v); // 出边走完，此刻 v 的完成时间最晚
                sv.pop_back();
                si.pop_back();
                continue;
            }
            si.back() = i + 1;
            int u = g[v][i];
            if (!seen[u]) {
                seen[u] = 1;
                sv.push_back(u);
                si.push_back(0);
            }
        }
    }
}

int main() {
    if (scanf("%d", &n) != 1) {
        return 0;
    }
    g.assign(n, vector<int>());
    rg.assign(n, vector<int>());
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        while (x) { // 0 是名单结束符
            g[i].push_back(x - 1);
            rg[x - 1].push_back(i);
            scanf("%d", &x);
        }
    }

    vector<int> order;
    finish_order(order);

    // 第二遍在反图上按完成时间逆序 DFS
    vector<int> comp(n, -1);
    for (int t = (int)order.size() - 1; t >= 0; t--) {
        int start = order[t];
        if (comp[start] != -1) {
            continue;
        }
        comp[start] = start;
        vector<int> stk;
        stk.push_back(start);
        while (!stk.empty()) {
            int v = stk.back();
            stk.pop_back();
            for (int i = 0; i < (int)rg[v].size(); i++) {
                int u = rg[v][i];
                if (comp[u] == -1) {
                    comp[u] = start;
                    stk.push_back(u);
                }
            }
        }
    }

    vector<char> present(n, 0), has_in(n, 0), has_out(n, 0);
    int comps = 0;
    for (int v = 0; v < n; v++) {
        if (!present[comp[v]]) {
            present[comp[v]] = 1;
            comps++;
        }
        for (int i = 0; i < (int)g[v].size(); i++) {
            int u = g[v][i];
            if (comp[v] != comp[u]) { // 分量内部的边缩点后消失
                has_out[comp[v]] = 1;
                has_in[comp[u]] = 1;
            }
        }
    }
    int sources = 0, sinks = 0;
    for (int v = 0; v < n; v++) {
        if (present[v]) {
            if (!has_in[v]) sources++;
            if (!has_out[v]) sinks++;
        }
    }
    int merged = (comps == 1) ? 0 : (sources > sinks ? sources : sinks);
    printf("%d\n%d\n", sources, merged);
    return 0;
}

python

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
83
84
85
86
87
88
89
90
91
92#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 01:09
# update_at: 2026-10-02 01:09

import sys
from collections.abc import Iterator


def read_graph(n: int, nums: Iterator[int]) -> list[list[int]]:
    """按题面格式读出邻接表：每所学校的名单以 0 结束，只有一个 0 表示空名单。"""
    graph: list[list[int]] = []
    for _ in range(n):
        cur: list[int] = []
        while (x := next(nums)):        # 0 是名单结束符，0 之前的都是被支援的学校
            cur.append(x - 1)           # 题面点号从 1 开始，统一转成 0 开始
        graph.append(cur)
    return graph


def finish_order(graph: list[list[int]]) -> list[int]:
    """第一遍 DFS（迭代版）：返回全部点，按「完成时间」从早到晚排列（越晚完成越靠后）。"""
    seen = [False] * len(graph)
    order: list[int] = []
    for root in range(len(graph)):
        if seen[root]:
            continue
        seen[root] = True
        stack = [(root, 0)]             # (点, 下一条待走出去的边的下标)
        while stack:
            v, i = stack[-1]
            if i == len(graph[v]):      # 出边走完，此刻 v 的完成时间最晚
                order.append(v)
                stack.pop()
                continue
            stack[-1] = (v, i + 1)      # 先记下"这条边用过了"，再决定是否递归下去
            if not seen[u := graph[v][i]]:
                seen[u] = True
                stack.append((u, 0))
    return order


def component_of(graph: list[list[int]], order: list[int]) -> list[int]:
    """第二遍在反图上按完成时间逆序 DFS，得到每点所属强连通分量（用分量内代表点编号）。"""
    reverse = [[] for _ in graph]
    for v, nbrs in enumerate(graph):
        for u in nbrs:
            reverse[u].append(v)

    comp = [-1] * len(graph)
    for start in reversed(order):
        if comp[start] != -1:
            continue
        comp[start] = start             # 分量编号取该分量里完成最晚的点，天然不重复
        stack = [start]
        while stack:
            for u in reverse[stack.pop()]:
                if comp[u] == -1:
                    comp[u] = start
                    stack.append(u)
    return comp


def condensation_degrees(graph: list[list[int]], comp: list[int]) -> tuple[int, int]:
    """缩点后退化为 DAG，返回入度为 0 的分量数与出度为 0 的分量数。"""
    has_in = {c: False for c in comp}
    has_out = {c: False for c in comp}
    for v, nbrs in enumerate(graph):
        for u in nbrs:
            if comp[v] != comp[u]:      # 分量内部的边缩点后消失，不影响度数
                has_out[comp[v]] = True
                has_in[comp[u]] = True
    return (sum(not has_in[c] for c in has_in), sum(not has_out[c] for c in has_out))


def solve() -> None:
    data = map(int, sys.stdin.buffer.read().split())
    n = next(data)

    graph = read_graph(n, data)
    comp = component_of(graph, finish_order(graph))
    sources, sinks = condensation_degrees(graph, comp)

    # 全图只有一个强连通分量时本身已互通，加 0 条边即可；否则把 max(源,汇) 当作答案
    merged = 0 if len(set(comp)) == 1 else max(sources, sinks)
    print(sources, merged, sep='\n')


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：两遍 DFS 与一次度数统计都是 $O(n + m)$ ，合计 $O(n + m)$ ，其中 $m$ 是支援关系条数（ $m \leqslant n^2$ ）。 $n \leqslant 100$ 时开销可忽略。
空间复杂度：邻接表、反图、seen / comp 数组与 DFS 栈，合计 $O(n + m)$ 。

总结

本题的两个问题都是强连通分量缩点后的度数统计：

第一问 = 源分量数 $S$ 。因为源分量既"收不到"别人，又是所有点的可达性来源。
第二问 = 分量数大于 1 时 $\max(S, T)$ 。下界来自"每个源要补入边、每个汇要补出边，一条边只能同时补一对"，上界来自"源汇配对连成环"的构造；只有一个分量时答案为 $0$ ，必须单独判断。

算法本身（Kosaraju 两遍 DFS）是 $O(n+m)$ ，瓶颈只在实现细节上：迭代 DFS 的完成时间、反图上的第二遍遍历、以及"单分量特判不能写成 $S = T = 1$ "。

图示解析

下面用样例把 Kosaraju 的两遍 DFS 走完，说明"完成时间"和"分量编号"是怎么来的。原图如下， $1 \to 2 \to 5 \to 1$ 构成一个三元环， $3$ 和 $4$ 只有入边。

flowchart LR
  v1["1"] --> v2["2"]
  v1 --> v4["4"]
  v1 --> v3["3"]
  v2 --> v4
  v2 --> v5["5"]
  v5 --> v1

方框编号就是学校编号，箭头方向就是支援方向。

第一遍在原图上从 $1$ 开始 DFS：走进 $2$ ，再走进 $4$ （ $4$ 无出边，完成），回到 $2$ 之后走进 $5$ ， $5$ 走到已访问的 $1$ ，于是 $5$ 完成、 $2$ 完成；回到 $1$ 再走进 $3$ ， $3$ 完成；最后 $1$ 完成。完成顺序是 $4, 5, 2, 3, 1$ 。

步骤	当前栈	刚完成的点	累计完成顺序
走出 $1 \to 2 \to 4$	$1, 2, 4$	$4$	$4$
$2 \to 5$ ， $5 \to 1$ 已访问	$1, 2, 5$	$5$	$4, 5$
$2$ 无剩余出边	$1, 2$	$2$	$4, 5, 2$
$1 \to 3$	$1, 3$	$3$	$4, 5, 2, 3$
$1$ 无剩余出边	$1$	$1$	$4, 5, 2, 3, 1$

第二遍按完成时间从晚到早（即 $1, 3, 2, 5, 4$ ）在反图上 DFS：从 $1$ 出发，反边 $1 \to 5$ 、 $5 \to 2$ 、 $2 \to 1$ 把 $\{1, 2, 5\}$ 一次收完，这就是分量 $A$ ，编号取起点 $1$ ；接着 $3$ 未访问，单独成分量 $B$ ；最后 $4$ 单独成分量 $C$ 。缩点后即得到上文 $A \to B$ 、 $A \to C$ 的图，于是 $S = 1$ 、 $T = 2$ 。

第二遍的起点	反图上能走到的点	分量编号
$1$	$1, 2, 5$	$A = 1$
$3$	$3$	$B = 3$
$4$	$4$	$C = 4$

读表时注意两点：完成顺序里 $1$ 排最后，所以它成为第二遍的第一个起点——这正是"完成时间最晚的点落在源头侧分量"的直观体现；而 $4$ 完成得最早、在第二遍里反而最后被处理，因为它在原图里是纯粹的汇点。

【题目描述】

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

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

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

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

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

【输入格式】

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

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

【输出格式】

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

【数据范围】

$2 \le N \le 100$

【输入样例】

text

【输出样例】

text

1
21
2

来源

《算法竞赛进阶指南》
acwing 可能含有视频讲解