「一本通 3.5 练习 2」消息的传递

形式化题目

给定 $n$ 个点的有向图 $G=(V,E)$ （ $C_{i,j}=1$ 表示存在有向边 $i \to j$ ），求最小的起点集合 $S \subseteq V$ ，使得从 $S$ 出发沿有向边可达的点覆盖全部 $n$ 个点，输出 $|S|$ 。

样例中 8 个点的传递关系为： $1 \to 3$ ， $2 \to 1,\ 2 \to 4$ ， $3 \to 2,\ 3 \to 4,\ 3 \to 5$ ， $4 \to 6$ ， $5 \to 4$ ， $6 \to 4$ ， $7 \to 4,\ 7 \to 8$ ， $8 \to 7$ ，输出 $2$ 。

正解

思路

朴素想法：逐点 BFS 求单点可达集，再贪心选覆盖最多的点、删掉已覆盖点反复进行。这既没有利用图的结构，贪心本身也不保证最优——问题的正确粒度根本不是"点"。

关键观察：互相可达的点是不可分割的传播单元。 若 $u$ 与 $v$ 互相可达，传给其中一个，另一个必然收到；所以把每个强连通分量（SCC）收缩成一个超级点、保留跨分量的边，得到的缩点 DAG（凝聚图无环）才是应该处理的对象，且这种缩点不改变可达关系、不改变最优解。

缩点之后问题退化为 DAG 上的平凡计数：

必要性：入度为 0 的分量没有任何分量能到达它，不在其中放起点，该分量内的点永远收不到消息——每个源点分量至少放一个起点。
充分性：对任意分量 $T$ ，若 $T$ 不是源点，沿入边不断逆推 $T \to T_1 \to T_2 \to \cdots$ ；DAG 无环，这条链必在有限步后停在某个源点 $S$ 。起点放在 $S$ ，消息顺着缩点路径就能传到 $T$ 。因此只选源点足以覆盖全图。

上下界相等，答案 = 缩点 DAG 中入度为 0 的强连通分量个数。缩点用经典 Kosaraju 算法：第一遍在正图上按后序（离开时间）记录所有点，第二遍在反图上按后序倒序起跑 DFS，每棵 DFS 树恰好是一个 SCC。下图是本题"缩点 + 数源点"的整体流程：

flowchart LR
    A["正图 + 反图邻接表"] --> B["Kosaraju 第一遍：正图迭代 DFS 求后序"]
    B --> C["第二遍：反图按倒序 DFS 染色 → 每树一个 SCC"]
    C --> D["扫跨分量边，给目标分量记入度"]
    D --> E["答案 = 入度为 0 的分量数"]

两遍 DFS 都写成显式栈（记录"当前点还有第几条边没走"）， $n=1000$ 的链状深图也不会触顶 Python 递归深度限制。

代码

solve() 读矩阵同时建正/反邻接表；post_order / assign_components 分别对应 Kosaraju 的两遍 DFS；最后的双重循环只统计跨分量边（ $comp[u]=comp[v]$ 的分量内边与自环不产生 DAG 入度）。

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

import sys


def post_order(graph: list[list[int]]) -> list[int]:
    """Kosaraju 第一遍：迭代 DFS 全图，按离开时间（后序）记录每个点。"""
    n = len(graph)
    seen = [False] * n
    order: list[int] = []
    for start in range(n):
        if seen[start]:
            continue
        seen[start] = True
        stack = [(start, 0)]  # (点, 下一条待访问的边下标)
        while stack:
            u, i = stack[-1]
            if i < len(graph[u]):          # 还有邻居没看过：压入下一个邻居
                stack[-1] = (u, i + 1)
                v = graph[u][i]
                if not seen[v]:
                    seen[v] = True
                    stack.append((v, 0))
            else:                          # 邻居耗尽：后序出栈
                stack.pop()
                order.append(u)
    return order


def assign_components(rg: list[list[int]], order: list[int]) -> list[int]:
    """Kosaraju 第二遍：按离开时间倒序在反图上 DFS，每棵 DFS 树缩成一个强连通分量，返回每个点的分量编号。"""
    comp = [-1] * len(rg)
    comp_id = 0
    for start in reversed(order):
        if comp[start] != -1:
            continue
        comp[start] = comp_id
        stack = [start]
        while stack:
            u = stack.pop()
            for v in rg[u]:
                if comp[v] == -1:
                    comp[v] = comp_id
                    stack.append(v)
        comp_id += 1
    return comp


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

    # 邻接表 + 逆邻接表：矩阵按行读，g[i] 存 i 能直接传到的点，rg 存反向边
    g: list[list[int]] = [[] for _ in range(n)]
    rg: list[list[int]] = [[] for _ in range(n)]
    for u in range(n):
        for v in range(n):
            if next(it):  # C[u][v] == 1 表示 u 能直接传给 v
                g[u].append(v)
                rg[v].append(u)

    # 缩点成 DAG：入度为 0 的强连通分量必须各传一个起始奸细
    comp = assign_components(rg, post_order(g))
    has_in = [False] * (max(comp) + 1 if n else 0)
    for u in range(n):
        cu = comp[u]
        for v in g[u]:
            if comp[v] != cu:  # 跨分量边给目标分量记一次入度
                has_in[comp[v]] = True

    print(has_in.count(False))


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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155/**
 * 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-05 05:50
 * update_at: 2026-10-05 05:50
 */

// main.cpp：roj 1516「一本通 3.5 练习 2」消息的传递
// 互相可达的奸细属于同一个传播单元，先 Kosaraju 求强连通分量并缩点，
// 缩点得到 DAG 后，入度为 0 的分量没有人能传消息进来，必须各选一个起点；
// 其余分量沿入边逆推必定停在某个源点分量，所以答案就是入度为 0 的分量个数。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXM = 1000005; // 边数最多 n^2 = 1e6

typedef long long ll;

// 链式前向星：正图为 head/to/nxt，反图为 rhead/rto/rnxt
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
int rhead[MAXN], rto[MAXM], rnxt[MAXM], redge_cnt;

ll n;
int comp[MAXN];     // comp[v] = 点 v 所属的强连通分量编号，0 表示还没染色
int has_in[MAXN];   // has_in[c] = 分量 c 在缩点 DAG 中是否存在入边
bool vis[MAXN];     // 第一遍 DFS 的访问标记
int order_[MAXN];   // 第一遍 DFS 按离开时间记录的后序序列
int order_cnt;
int stk[MAXN];      // 迭代 DFS 的显式栈，保存当前搜索路径上的点
int edge_ptr[MAXN]; // edge_ptr[u] = 点 u 下一条待走的出边编号
ll ans;

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

// 反图加一条 u -> v 的边，对应正图中的 v -> u。
void add_redge(int u, int v) {
    redge_cnt++;
    rto[redge_cnt] = v;
    rnxt[redge_cnt] = rhead[u];
    rhead[u] = redge_cnt;
}

// Kosaraju 第一遍：在正图上 DFS，一个点的全部出边走完才记入后序序列。
// n 最大 1000，用显式栈迭代实现，避免依赖递归深度。
void dfs_order(int s) {
    int top = 0;
    stk[top++] = s;
    vis[s] = true;
    edge_ptr[s] = head[s];
    while (top > 0) {
        int u = stk[top - 1];
        int e = edge_ptr[u];
        if (e != 0) {
            edge_ptr[u] = nxt[e]; // 回溯到 u 时从下一条出边继续
            int v = to[e];
            if (!vis[v]) {
                vis[v] = true;
                edge_ptr[v] = head[v];
                stk[top++] = v;
            }
        } else {
            // 出边全部走完，点 u 可以确定后序位置
            top--;
            order_cnt++;
            order_[order_cnt] = u;
        }
    }
}

// Kosaraju 第二遍：按后序倒序在反图上 DFS，每棵 DFS 树就是一个强连通分量。
void dfs_assign(int s, int cid) {
    int top = 0;
    stk[top++] = s;
    comp[s] = cid;
    while (top > 0) {
        int u = stk[--top];
        for (int e = rhead[u]; e != 0; e = rnxt[e]) {
            int v = rto[e];
            if (comp[v] == 0) {
                comp[v] = cid;
                stk[top++] = v;
            }
        }
    }
}

void solve() {
    cin >> n;

    // 读入 n x n 的传递矩阵：矩阵里为 1 表示 i 能直接传给 j，同时建正图和反图
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            if (x == 1) {
                add_edge(i, j);
                add_redge(j, i);
            }
        }
    }

    // 第一遍：正图上求每个点的后序
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs_order(i);
        }
    }

    // 第二遍：按后序倒序在反图上染强连通分量编号，编号从 1 开始
    int cid = 0;
    for (int i = order_cnt; i >= 1; i--) {
        int u = order_[i];
        if (comp[u] == 0) {
            cid++;
            dfs_assign(u, cid);
        }
    }

    // 扫跨分量边，给目标分量记入度；分量内部的边（含自环）不算入度
    for (int u = 1; u <= n; u++) {
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (comp[u] != comp[v]) {
                has_in[comp[v]] = 1;
            }
        }
    }

    // 缩点 DAG 中入度为 0 的分量各需要一个起点
    ans = 0;
    for (int c = 1; c <= cid; c++) {
        if (has_in[c] == 0) {
            ans++;
        }
    }
    cout << ans << endl;
}

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

    solve();

    return 0;
}

复杂度

时间复杂度： $O(n^2)$ 。读入矩阵本身是 $\Theta(n^2)$ ；建表、两遍 DFS、扫边统计各 $O(n+m)$ ， $m \leqslant n^2 = 10^6$ ，与 C++ 正解同阶。
空间复杂度： $O(n^2)$ 。正反两张邻接表最坏共 $2m$ 个下标；实测最大测例（ $n=1000$ ）峰值 57.5 MB，低于 128 MB 限制。

总结

本题是"最少起点使全图可达"的标准结论题：处理单位是强连通分量而不是点。互相可达的点在传播意义上等价，缩点成 DAG 后，必要性（源点进不来）与充分性（非源点沿入边逆推必达源点）夹逼出唯一答案——缩点后入度为 0 的分量个数。实现上用 Kosaraju 两遍迭代 DFS 找 SCC，再扫一遍跨分量边计数即可；注意分量内部的边（含自环）不能计入度。实测 10 组真实数据全部一致，最大测例 0.092 s / 57.5 MB，相对 1000 ms / 128 MB 限制十分宽裕。

图示解析

先看样例原图的 SCC 划分： $1 \to 3 \to 2 \to 1$ 构成环， $7 \to 8 \to 7$ 构成环， $4 \leftrightarrow 6$ （经 $4 \to 6$ 、 $6 \to 4$ 互达）， $5$ 单独成点。因此 8 个点缩成 4 个分量：

graph LR
    subgraph S1["SCC A: {1, 2, 3}"]
        n1["1"] --> n3["3"]
        n3 --> n2["2"]
        n2 --> n1
    end
    subgraph S2["SCC B: {5}"]
        n5["5"]
    end
    subgraph S3["SCC C: {4, 6}"]
        n4["4"] --> n6["6"]
        n6 --> n4
    end
    subgraph S4["SCC D: {7, 8}"]
        n7["7"] --> n8["8"]
        n8 --> n7
    end
    n3 --> n5
    n3 --> n4
    n2 --> n4
    n5 --> n4
    n7 --> n4

缩点后的 DAG 与入度如下（注意 $4 \to 6$ 是 SCC C 的内部边，不出现在 DAG 中）：

graph LR
    A["A {1,2,3}<br/>入度 0"] --> B["B {5}<br/>入度 1"]
    A --> C["C {4,6}<br/>入度 3"]
    B --> C
    D["D {7,8}<br/>入度 0"] --> C

观察重点：入度为 0 的分量只有 A 和 D，所以答案为 $2$ ——告诉 $\{1,2,3\}$ 中任意一人、 $\{7,8\}$ 中任意一人即可传遍全图；B、C 都能沿 $A \to B \to C$ 、 $A \to C$ 、 $D \to C$ 的路径被覆盖，无需再传。这与样例输出 $2$ 一致。