「一本通 3.5 练习 1」网络协议

形式化题目

给定一个包含 $n$ 个顶点的有向图 $G = (V, E)$ 。求：

任务 A：选取最少的起点集合 $S \subseteq V$ ，使得从 $S$ 出发能够遍历全图所有顶点。
任务 B：最少添加多少条有向边，使得整张图变成强连通图（任意两点之间互相可达）。

正解

思路

1. 强连通分量与 DAG 缩点

在有向图中，如果一组顶点两两互相可达，则它们构成一个强连通分量（SCC）。显然：

如果一个强连通分量内的某个节点获得了软件，那么该分量内的所有节点都可以通过内部路径获得软件。
如果新加的边连向分量内的任意一个节点，整个分量都能联通。

因此，我们可以利用 Tarjan 算法 找出所有的强连通分量，并将每个分量缩成一个超级节点，原本跨分量的边保留，得到一个有向无环图（DAG）。

2. 任务 A：最少分发软件数

在缩点后的 DAG 中：

如果一个节点的入度为 $0$ （称作起点分量/源点），没有任何其他节点能够到达它。因此，必须至少给每个入度为 $0$ 的分量中的某一个学校直接提供软件。
只要给所有入度为 $0$ 的分量分发软件，由于 DAG 中任意非零入度的节点都可以由某个入度为 $0$ 的节点顺着有向边到达，全图所有学校就都能获得软件。

因此，任务 A 的答案即为缩点后 DAG 中入度为 $0$ 的强连通分量个数。

3. 任务 B：使图强连通最少添加的边数

设缩点后的强连通分量总数为 $scc\_cnt$ ：

特判：如果 $scc\_cnt = 1$ ，说明原图本身已经是强连通图，无需添加任何边，答案为 $0$ 。
一般情况：设入度为 $0$ 的分量数为 $P$ ，出度为 $0$ 的分量数为 $Q$ 。
- 每个出度为 $0$ 的分量（汇点）都必须连出至少一条边，否则它无法到达其他分量；
- 每个入度为 $0$ 的分量（源点）都必须有至少一条边连入，否则其他分量无法到达它。
- 要将 DAG 变成强连通图，我们应当尽量将出度为 $0$ 的汇点连向入度为 $0$ 的源点，形成一个大的环流。每次添加一条从出度为 $0$ 连向入度为 $0$ 的边，可以同时解决一个出度为 $0$ 和一个入度为 $0$ 的需求。
- 剩余未配对的孤立入度或出度分量，分别再各连一条边，即可使得整个图强连通。
- 因此，最少需要添加的边数为 $\max(P, Q)$ 。

代码

Python 版：

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#!/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-09-30 15:45
# update_at: 2026-09-30 15:45

import sys


def tarjan_scc(n: int, adj: list[list[int]]) -> list[int]:
    """计算有向图每个节点的强连通分量编号（0-indexed）。"""
    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    scc = [0] * (n + 1)
    stk: list[int] = []
    in_stk = [False] * (n + 1)
    timer = scc_cnt = 0

    def dfs(u: int) -> None:
        nonlocal timer, scc_cnt
        timer += 1
        dfn[u] = low[u] = timer
        stk.append(u)
        in_stk[u] = True

        for v in adj[u]:
            if not dfn[v]:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif in_stk[v]:
                low[u] = min(low[u], dfn[v])

        if low[u] == dfn[u]:
            while True:
                top = stk.pop()
                in_stk[top] = False
                scc[top] = scc_cnt
                if top == u:
                    break
            scc_cnt += 1

    for i in range(1, n + 1):
        if not dfn[i]:
            dfs(i)

    return scc, scc_cnt


def solve() -> None:
    tokens = iter(sys.stdin.read().split())
    try:
        n = int(next(tokens))
    except StopIteration:
        return

    adj = [[] for _ in range(n + 1)]
    for u in range(1, n + 1):
        while True:
            v = int(next(tokens))
            if v == 0:
                break
            adj[u].append(v)

    scc, scc_cnt = tarjan_scc(n, adj)

    if scc_cnt == 1:
        print(1)
        print(0)
        return

    # 统计缩点后 DAG 中各 SCC 的入度与出度
    in_deg = [0] * scc_cnt
    out_deg = [0] * scc_cnt
    for u in range(1, n + 1):
        for v in adj[u]:
            if scc[u] != scc[v]:
                in_deg[scc[v]] += 1
                out_deg[scc[u]] += 1

    zero_in = sum(1 for d in in_deg if d == 0)
    zero_out = sum(1 for d in out_deg if d == 0)

    print(zero_in)
    print(max(zero_in, zero_out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
116
117
118
119
120
121
122
123
124/**
 * 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-04 22:30
 * update_at: 2026-10-05 05:43
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXM = 10005;

typedef long long ll;

// n 个学校，m 条支援关系
ll n, m;

// 链式前向星存图
int head[MAXN], nxt[MAXM], to[MAXM], edge_cnt;

// Tarjan 所需：dfn 时间戳、low 追溯值、栈内标记、栈、分量编号
int dfn[MAXN], low[MAXN], stk[MAXN];
bool in_stk[MAXN];
int timer_cnt, top_cnt, scc_cnt;
int scc_id[MAXN]; // scc_id[u] 表示节点 u 所属的强连通分量编号

// 缩点后 DAG 中每个分量的入度与出度
int in_deg[MAXN], out_deg[MAXN];

// 加一条 u -> v 的有向边。
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// Tarjan 求强连通分量。
void tarjan(int u) {
    timer_cnt++;
    dfn[u] = low[u] = timer_cnt;
    top_cnt++;
    stk[top_cnt] = u;
    in_stk[u] = true;

    for (int i = head[u]; i != 0; i = nxt[i]) {
        int v = to[i];
        if (dfn[v] == 0) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    // u 是当前强连通分量的根，弹出整个分量并编号
    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int v = stk[top_cnt];
            top_cnt--;
            in_stk[v] = false;
            scc_id[v] = scc_cnt;
            if (v == u) break;
        }
    }
}

void read_input() {
    cin >> n;
    m = 0;
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        int v;
        while (cin >> v && v != 0) {
            add_edge(i, v);
            m++;
        }
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (dfn[i] == 0) tarjan(i);
    }

    // 统计缩点后 DAG 中每个分量的入度与出度（只算跨分量的边）
    for (int u = 1; u <= n; u++) {
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (scc_id[u] != scc_id[v]) {
                out_deg[scc_id[u]]++;
                in_deg[scc_id[v]]++;
            }
        }
    }

    // P 为入度为 0 的分量数，Q 为出度为 0 的分量数
    int p = 0, q = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (in_deg[i] == 0) p++;
        if (out_deg[i] == 0) q++;
    }

    // 任务 A：给所有入度为 0 的分量发软件即可覆盖全图
    cout << p << "\n";
    // 任务 B：整个图已强连通时不用加边，否则答案是 max(P, Q)
    if (scc_cnt == 1)
        cout << 0 << "\n";
    else
        cout << max(p, q) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(n + m)$ 。Tarjan 算法对图遍历一次的时间为 $\mathcal{O}(n + m)$ ，统计缩点后入度和出度的时间为 $\mathcal{O}(n + m)$ 。由于 $n \le 100$ ， $m \le n(n - 1) \le 10^4$ ，可以在毫秒级完成。
空间复杂度： $\mathcal{O}(n + m)$ 。邻接表、Tarjan 栈、DFS 深度数组以及缩点度数数组的开销均为 $\mathcal{O}(n + m)$ 。

总结

本题是典型的有向图强连通分量缩点应用题。通过 Tarjan 算法将原图的有向环收缩为单点，将原图转化为结构简单的有向无环图（DAG）。任务 A 本质是 DAG 的源点计数；任务 B 本质是将 DAG 转化为强连通图的最小加边问题，其关键结论是当分量数大于 1 时，答案为源点数与汇点数的较大值 $\max(P, Q)$ 。

图示解析

以样例输入为例：

学校 $1$ 支援 $2, 4, 3$ ；学校 $2$ 支援 $4, 5$ ；学校 $3$ 无支援；学校 $4$ 无支援；学校 $5$ 支援 $1$ 。
顶点 $1, 2, 5$ 构成一个环： $1 \to 2 \to 5 \to 1$ ，属于同一个强连通分量 $S_1 = \{1, 2, 5\}$ 。
顶点 $3$ 和顶点 $4$ 分别独立，各自构成强连通分量 $S_2 = \{3\}$ 和 $S_3 = \{4\}$ 。

graph TD
    subgraph S1 ["SCC 1: {1, 2, 5}"]
        1 --> 2
        2 --> 5
        5 --> 1
    end
    subgraph S2 ["SCC 2: {3}"]
        3
    end
    subgraph S3 ["SCC 3: {4}"]
        4
    end

    1 --> 3
    1 --> 4
    2 --> 4

缩点后的 DAG 结构如下：

graph LR
    S1["SCC 1 (入度=0, 出度=2)"] --> S2["SCC 2 (入度=1, 出度=0)"]
    S1 --> S3["SCC 3 (入度=1, 出度=0)"]

入度为 0 的分量集合： $\{S_1\}$ ，共 $1$ 个，任务 A 答案为 $1$ 。
出度为 0 的分量集合： $\{S_2, S_3\}$ ，共 $2$ 个。
任务 B 答案为 $\max(1, 2) = 2$ 。添加边 $3 \to 1$ 和 $4 \to 1$ 即可使全图强连通。