形式化题目

给定 $n$ 个点和若干有向边：第 $i$ 个点指向 $j$ 表示 $i$ 允许把资料传给 $j$。资料放在某个点上后会沿有向边自动传播，一张光盘覆盖放置点可达的全部点（含放置点自身）。求让所有点都获得资料所需的最少光盘数。

正解

思路

第一步：把"拷贝"翻译成可达性。 “若 $A$ 愿意给 $B$、$B$ 愿意给 $C$，则 $A$ 拿到后 $B$、$C$ 都能拿到”——这正是有向图上路径的定义。所以一张光盘放在 $p$ 手里，最终覆盖的恰好是 $p$ 的可达集 $\mathrm{reach}(p)$（含 $p$ 自己）。问题变成：选最少的起点，让它们的可达集之并盖住所有点。

第二步：找到"必须直接拿光盘"的点。 强连通分量（SCC）内部互相可达：光盘放在分量内任何一人手里，覆盖效果完全相同。把每个 SCC 缩成一个点，得到一个 DAG。入度为 $0$ 的分量（源分量）拿不到任何人传来的资料——若外部点能把资料传进源分量 $S$，传进来的最后一条边就是一条从其他分量指向 $S$ 的边，与 $S$ 入度为 $0$ 矛盾。因此：

• 下界：每个源分量必须有人直接持有光盘；不同源分量互相不可达，一张光盘至多覆盖一个源分量，故至少需要（源分量个数）张。
• 上界：DAG 中任何分量沿边倒退走，总能到达某个入度为 $0$ 的分量；给每个源分量各放一张，资料顺流而下覆盖全部分量，故（源分量个数）张足够。

答案 = 缩点 DAG 中入度为 $0$ 的强连通分量个数。 以样例为例（边 $1\to2,1\to3,1\to4,2\to4,2\to5,5\to1$）：

graph LR
    subgraph S1["分量 A = {1, 2, 5}"]
        a1["1"] --> a2["2"]
        a2 --> a5["5"]
        a5 --> a1
    end
    S1 -->|"1→3"| s3["分量 B = {3}"]
    S1 -->|"1→4、2→4"| s4["分量 C = {4}"]

$1\to2\to5\to1$ 构成环，把 $1,2,5$ 缩成源分量 $A$；$B$、$C$ 都有来自 $A$ 的入边，只有 $A$ 入度为 $0$。在 $A$ 中任选一人（如 1 号）放光盘，$1$ 能到 $\{2,3,4,5\}$，全覆盖，答案为 $1$。

第三步：用 bitset 传递闭包数出源分量。 $n \leqslant 200$，不必写 Tarjan；传递闭包配 Python 大整数（天然 bitset）反而更短更快：

• reach[i]：$i$ 能到达的点集（显式并入自环）。
• Floyd 式闭包：若 reach[i] 第 $k$ 位为 1，则整行 reach[i] |= reach[k]。
• pred[i]（能到达 $i$ 的点集）就是闭包矩阵的第 $i$ 列。
• 强连通分量即互相可达的点集：$\mathrm{SCC}(i) = \mathrm{reach}[i] \mathbin{\&} \mathrm{pred}[i]$（两个集合都含 $i$ 自身）。

判定"源"只需要一个位运算：

$\mathrm{SCC}(i)$ 是源 $\iff \mathrm{pred}[i] \subseteq \mathrm{reach}[i]$，即"所有能到 $i$ 的点，$i$ 反过来也能到"。

若 $\mathrm{SCC}(i)$ 非源，必有外部点 $j$ 能到 $i$ 而 $i$ 到不了 $j$（$j$ 进入该分量的路径存在，$i$ 却无法反向出去），此时 pred[i] & ~reach[i] 非空；反之，能到 $i$ 的点全部落在 $\mathrm{SCC}(i)$ 内，说明没有任何外部路径能进入该分量，它是源。

对样例逐人检查（集合均含自环）：

同一源分量的所有成员都通过检查且 $\mathrm{SCC}$ 掩码相同，非源分量的成员全部不通过，所以把通过者的 reach[i] & pred[i] 放进集合并计数，得到的就是源分量个数——样例去重后只剩 $\{1,2,5\}$，输出 $1$。

代码

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

import sys


def transitive_closure(adj: list[int]) -> list[int]:
    """bitset 版 Floyd 传递闭包：reach[i] = i 能到达的点集（含自己）的位掩码。"""
    reach = adj[:]
    for k in range(len(reach)):
        rk = reach[k]
        # i 能到 k，就能到 k 能到的一切：一次大整数 OR 完成整行转移
        reach = [r | rk if r >> k & 1 else r for r in reach]
    return reach


def count_source_sccs(reach: list[int], pred: list[int]) -> int:
    """统计"源"强连通分量个数：能到 i 的点都能被 i 反向到达，说明没有外部边进入 i 所在分量。"""
    return len({reach[i] & pred[i] for i in range(len(reach)) if not pred[i] & ~reach[i]})


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    adj: list[int] = []
    for i in range(n):
        bits = 1 << i  # 自己算进可达集，闭包与 SCC 判断都依赖这一点
        while j := next(data):  # 每行以 0 结尾
            bits |= 1 << (j - 1)
        adj.append(bits)

    reach = transitive_closure(adj)
    pred = [sum(1 << j for j in range(n) if reach[j] >> i & 1) for i in range(n)]  # reach 的第 i 列
    print(count_source_sccs(reach, pred))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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 00:20
 * update_at: 2026-10-05 00:20
 */
#include <cstdio>
#include <bitset>
using namespace std;

typedef long long ll;

const int MAXN = 205;

// 题目含义：第 i 个营员愿意把资料拷贝给他这一行给出的营员。
// 一张光盘放在 p 手里，能覆盖的正是 p 在有向图上可达的所有点（含 p 自己）。
// 答案 = 缩点后有向无环图中入度为 0 的强连通分量（源分量）个数。

bitset<MAXN> reach[MAXN]; // reach[i] = i 能到达的点集（含 i 自己）的位掩码
bitset<MAXN> pred[MAXN];  // pred[i] = 能到达 i 的点集的位掩码，即闭包矩阵的第 i 列
char counted[MAXN];       // counted[i] = 1 表示 i 所在的源分量已经统计过，用于去重

int main() {
    ll n;
    scanf("%lld", &n);

    for (ll i = 1; i <= n; i++) {
        reach[i].set(i); // 自己也算可达，闭包与 SCC 判定都依赖这一点
        ll j;
        scanf("%lld", &j);
        while (j != 0) { // 每行以 0 结束
            reach[i].set(j);
            scanf("%lld", &j);
        }
    }

    // Floyd 式传递闭包：i 能到 k，就能到 k 能到的一切
    for (ll k = 1; k <= n; k++) {
        for (ll i = 1; i <= n; i++) {
            if (reach[i].test(k)) {
                reach[i] |= reach[k];
            }
        }
    }

    // 转置闭包矩阵：reach[j] 的第 i 位为 1，说明 j 能到 i，即 j 属于 pred[i]
    for (ll j = 1; j <= n; j++) {
        for (ll i = 1; i <= n; i++) {
            if (reach[j].test(i)) {
                pred[i].set(j);
            }
        }
    }

    // 统计源分量个数：SCC(i) = reach[i] & pred[i]。
    // pred[i] 中所有点都能被 i 反过来到达（pred[i] 是 reach[i] 的子集）时，
    // 没有任何外部边能进入 i 所在分量，它就是源分量；同一分量去重只算一次。
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        if (counted[i]) {
            continue;
        }
        if ((pred[i] & ~reach[i]).none()) {
            ans++;
            bitset<MAXN> scc = reach[i] & pred[i];
            for (ll j = 1; j <= n; j++) {
                if (scc.test(j)) {
                    counted[j] = 1;
                }
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度

• 时间：闭包为 $n$ 轮 Floyd，每轮 $n$ 次大整数 OR，每次 $O(n/w)$（$w$ 为位密度因子，CPython 约 30），总计 $O(n^3/w)$；取列与源判定各 $O(n^2)$。$n = 200$ 时约几万次字长级运算，实测单组数据约 0.02s，无 TLE 风险。这与本题 $O(n^3)$ 的 Floyd 闭包经典实现同阶；若数据规模更大，应改用 Tarjan/Kosaraju 求 SCC 后统计入度，$O(n+m)$。
• 空间：闭包矩阵 $O(n^2/w)$，约 5KB，远低于 128MB。

总结

• 题眼：一张光盘的覆盖范围 = 放置者的可达集；"无法被间接覆盖"的点恰好构成缩点 DAG 的源分量，最少光盘数 = 源分量个数。
• 判定技巧：bitset 闭包下，$\mathrm{SCC}(i) = \mathrm{reach}[i] \mathbin{\&} \mathrm{pred}[i]$，"是否源"化为一次 $\mathrm{pred}[i] \subseteq \mathrm{reach}[i]$ 判断，去重计数即答案。
• 同模型（缩点后数入度 0 分量）是图论常见套路：校园网络选服务器、Popular Cows 等都是它的变体；规模大时换 Tarjan/Kosaraju。