形式化题目

给定一张有向无环图 $G=(V,E)$，$|V|=N$、$|E|=M$，边可以重复给出。对每个点 $v$，求它能到达的点数

其中规定 $v$ 到自身可达，即 $v \in R(v)$，所以 $|R(v)| \geqslant 1$；重复的边不影响可达性。

正解

思路

本题 $1 \leqslant N,M \leqslant 30000$，时限 1000ms，内存 128MB。

第一步：把「搜索」看成「集合合并」。

最容易想到的做法是：对每个点单独做一次 DFS，把能走到的点全部标记，数标记个数。它是对的，因为 DFS 走遍的正是所有路径终点。但它的工作量是 $O(N^2)$：每个点都要重走一遍自己后方的整张子图，而不同起点的子图高度重叠。真实数据里这种重叠非常严重——第 5 组 $N=M=30000$、却只有一个点出度为 $0$，说明绝大多数点最终都汇入同一个汇点，同一份信息被重算了上万遍。

重复的根源是：DFS 每次都在重新发现 $w$ 能到哪些点，而不是复用已经知道的答案。于是把搜索改写成递推：

只要每个后继 $w$ 的 $R(w)$ 已经算好，$R(v)$ 就只是几个已知集合的并集。

第二步：用拓扑逆序让递推成立。

上面的式子依赖后继，所以要从汇点往源点算。DAG 的拓扑序保证了：把拓扑序倒过来扫，轮到 $v$ 时它的所有后继都已经算完。样例第 1 组的拓扑序是 $1,2,4,6,7,3,5,10,8,9$，倒过来扫的处理次序如下：

flowchart LR
    A["9"] --> B["8"] --> C["10"] --> D["5"] --> E["3"] --> F["7"] --> G["6"] --> H["4"] --> I["2"] --> J["1"]

图中每个节点是样例里的一个点，箭头方向是计算顺序，不是原图的边：从没有出边的汇点 $9,8,10$ 出发一路向左，最后才算到源点 $1,2$。观察重点是箭头只保证「后继排在前面」——例如 $2 \to 3$ 这条原图的边，在图上体现为 $3$ 出现在 $2$ 的左边，所以算 $2$ 的时候 $3$ 的掩码已经就位。原图真正的边见下面那张掩码表。

第三步：把一个集合压成一个整数。

即使改成递推，如果真用 Python 的 set 去合并，每个后继集合仍要逐个元素搬进来，$\sum_v |R(v)|$ 依然可以达到 $O(N^2)$：第 5 组数据的答案总和就是 $4.5\times10^8$，没有实质变快。

真正的转折在于：题目只问「某个点在不在 $R(v)$ 里」，从不问「$R(v)$ 里具体有哪些数」。既然一个集合只被用来回答「在不在」，那就把它编码成 $N$ 位二进制数 reach[v]，第 $u$ 位为 $1$ 表示 $u$ 可达。三种集合运算于是各对应一条位运算：

一次按位或只花 $O(N/64)$ 个机器字，并且由 Python 的 C 层执行，常数远小于在 Python 层逐个元素循环。

下面按处理次序列出样例第 1 组的全过程。去重后剩 8 条边：$2\to3,2\to5,2\to10,3\to8,3\to9,4\to8,4\to9,5\to9$。

表的每一行是一次循环：位掩码最左边是第 $10$ 位、最右边是第 $1$ 位（第 $0$ 位空着不用，于是点编号和位下标一一对应，读写时不需要做偏移换算）。看第 9 行 $v=2$：它先置上自己的第 $2$ 位，再或上进过 3、5、10 三行的掩码，得到 $6$ 个 $1$，正好对应样例输出的第 2 行 6；第 4 行 $v=5$ 只有 $5$ 和 $9$ 两个 $1$，对应输出 2。出度为 $0$ 的点 $1,6,7,8,9,10$ 在表里都只有一个 $1$，对应样例输出的 1。这里 $8$ 和 $9$ 并不是孤立点，只是没有出边——它们的掩码仍是别的点合并的对象。

第四步：及时释放掩码。

用大整数存集合的代价是：每个 reach[v] 都占 $N$ 位，$N$ 个同时驻留就是 $O(N^2)$ 位。做法是给每个点记一个「还有几个前驱要读它」的计数，读完就把它置 $0$ 释放。把释放那一行删掉再跑第 5 组数据，峰值内存从 31MB 涨到 149MB，直接超过 128MB 限制——这一步不是锦上添花，而是本题 Python 实现能不能过内存限制的关键。

代码里还有一个容易忽略的正确性要求：输入边要去重。题面没有声明边不重复，而样例第 1 组的 2 3 和 5 9 各出现了两次，真实数据前四组分别含 2、80、103、431 条重边。不去重的话入度会虚高，Kahn 算法里这些点的入度永远减不到 $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#!/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-01 12:55
# update_at: 2026-10-01 13:10

import sys


def topo_order(n: int, adj: list[list[int]], indeg: list[int]) -> list[int]:
    """Kahn 算法求拓扑序：反复取出入度为 0 的点，并消掉它伸出的每条边。

    只在内部副本上减入度，调用者的 indeg 原样保留，之后还要当引用计数用。
    """
    deg = indeg[:]
    order: list[int] = []
    queue = [v for v in range(1, n + 1) if deg[v] == 0]
    for u in queue:                    # queue 边遍历边增长，用法等价于 deque
        order.append(u)
        for v in adj[u]:
            deg[v] -= 1
            if deg[v] == 0:
                queue.append(v)
    return order


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

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    preds = [0] * (n + 1)              # preds[v]：v 的前驱个数，等于去重后的入度
    edges: set[tuple[int, int]] = set()
    for _ in range(m):
        edge = next(data), next(data)
        if edge in edges:              # 重边只留一条，否则前驱个数会被重复统计
            continue
        edges.add(edge)
        x, y = edge
        adj[x].append(y)
        preds[y] += 1

    # reach[v] 是一个大整数：第 u 位为 1 表示 v 能到达 u。
    # 每个掩码至少要留给 preds[v] 个前驱去读，读完（计数归零）就释放，
    # 否则 N 个 O(N) 位的大整数会同时驻留，内存会翻好几倍。
    reach = [0] * (n + 1)
    count = [0] * (n + 1)
    for v in reversed(topo_order(n, adj, preds)):  # 逆拓扑序：后继的 reach 都已算好
        mask = 1 << v                              # 先把自己放进去
        for w in adj[v]:
            mask |= reach[w]                       # 后继能到的点，v 也都能到
        count[v] = mask.bit_count()                # 二进制里 1 的个数就是可达点数
        for w in adj[v]:
            preds[w] -= 1
            if preds[w] == 0:
                reach[w] = 0                       # w 的前驱都读完了，掩码可以释放
        if preds[v]:
            reach[v] = mask

    sys.stdout.write('\n'.join(map(str, count[1:])))


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
78
79
80
81
82
83
84
85/**
 * 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-06 17:03
 * update_at: 2026-10-06 17:03
 */
// 可达性统计：DAG 上按拓扑逆序做位集合 DP，
// reach[v] 的第 u 位为 1 表示 v 能到达 u，合并后继用按位或。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 30005; // 点数上限
const int MAXM = 30005; // 边数上限

int n, m;
int head[MAXN];          // 链式前向星：head[v] 是 v 的第一条出边编号
int nxt[MAXM];           // 同起点下一条边
int to_[MAXM];           // 边的终点（避开 std 的 to）
int indeg[MAXN];         // 入度，用于 Kahn 拓扑排序
int topo[MAXN];          // topo[i] = 拓扑序第 i 个点
int cnt_topo = 0;        // 拓扑序长度（去重后应等于 n）
ll ans[MAXN];            // ans[v] = v 能到达的点数，最后按点编号输出

pair<int, int> edges[MAXM]; // 原始边，先排序去重再建图

bitset<MAXN> reach[MAXN]; // reach[v]：v 能到达的点集，第 u 位为 1 表示可达

// 加一条有向边 u -> v
void add_edge(int u, int v) {
    static int tot = 0;
    ++tot;
    to_[tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        edges[i] = make_pair(x, y);
    }

    // 题面允许重复边：先排序去重，否则入度虚高，拓扑排序会漏点
    sort(edges + 1, edges + m + 1);
    int m2 = unique(edges + 1, edges + m + 1) - (edges + 1);
    for (int i = 1; i <= m2; ++i) {
        add_edge(edges[i].first, edges[i].second);
        ++indeg[edges[i].second];
    }

    // Kahn 算法求拓扑序：入度为 0 的点先入队
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ++cnt_topo;
        topo[cnt_topo] = u;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to_[e];
            --indeg[v];
            if (indeg[v] == 0) q.push(v);
        }
    }

    // 拓扑逆序递推：轮到 v 时它的所有后继都已算完
    // R(v) = {v} ∪ R(w1) ∪ R(w2) ∪ ...
    for (int i = cnt_topo; i >= 1; --i) {
        int v = topo[i];
        reach[v][v] = 1; // 自己到自己也算可达
        for (int e = head[v]; e; e = nxt[e])
            reach[v] |= reach[to_[e]];
        ans[v] = (ll)reach[v].count(); // 数二进制里 1 的个数
    }

    // 输出按点编号 1..n 的顺序
    for (int v = 1; v <= n; ++v)
        printf("%lld\n", ans[v]);
    return 0;
}

复杂度

• 时间复杂度：$O\big((N+M)\cdot N/64\big)$。每条边做一次 $O(N/64)$ 的按位或，每个点做一次 $O(N/64)$ 的 bit_count()，前面还有 $O(N+M)$ 的读入、去重和拓扑排序。
• 空间复杂度：$O(N+M)$ 存图和顺序数组，另加同时驻留的掩码，最坏 $O(N^2/64)$ 个机器字；配合引用计数释放后，第 5 组数据实测峰值 31MB。

总结

• 看到「从每个点出发能到达多少点」，先写成集合递推 $R(v)=\{v\}\cup\bigcup R(w)$，把重复搜索变成合并已有答案。
• DAG 加上依赖后继，就说明该按拓扑逆序自底向上填，每个答案只算一次。
• 只问「在不在」的集合用位掩码：合并是按位或，大小是 bit_count()。Python 的任意精度整数天然就是一个位集合，不必手写 bitset。
• 输入边可能重复，去重是正确性要求而不只是优化：重边会让入度虚高，拓扑排序会漏点。
• 掩码很占空间，读完就按引用计数释放，是本题通过内存限制的必要处理。