图的遍历

题意

对有向图中的每个点 v，求从 v 出发能够到达的最大编号。

思路

从每个点各做一次搜索会达到 $O(n(n+m))$ 。把问题反过来：原图中 v 能到达 x，等价于反图中 x 能到达 v。

按 n,n-1,...,1 枚举候选最大编号 largest，从它在反图中搜索。凡是首次访问到的点，其答案就是 largest：

它在原图中可以到达 largest；
更大的候选已经先处理过却没有访问到它，所以它不可能到达更大编号。

一个点写入答案后不再入栈，因此所有搜索合计只访问每个点、每条反向边常数次。

Python 知识

reverse_graph[v].append(u) 直接建立反边 v -> u。
range(n,0,-1) 表达从大到小的处理顺序。
answer[node]==0 同时表示“尚未访问”，无需单独的 visited。
显式 stack 避免最长链导致递归层数超限。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：显式栈图遍历。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：递归深度注意点。

代码

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
29import sys


def main():
    read = sys.stdin.buffer.readline
    n, m = map(int, read().split())
    reverse_graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, read().split())
        reverse_graph[v].append(u)

    answer = [0] * (n + 1)
    for largest in range(n, 0, -1):
        if answer[largest]:
            continue
        answer[largest] = largest
        stack = [largest]
        while stack:
            node = stack.pop()
            for previous in reverse_graph[node]:
                if not answer[previous]:
                    answer[previous] = largest
                    stack.append(previous)

    print(*answer[1:])


if __name__ == "__main__":
    main()

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/**
 * P3916 图的遍历
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

const int MAXN = 100005;
const int MAXM = 100005;

// 反向图：反着建边，从大编号点 DFS 时就能一次性标记所有能到达它的点
int head[MAXN], to[MAXM], nxt[MAXM], cnt;
int ans[MAXN];
int n, m;

void add_edge(int u, int v) {
    ++cnt;
    to[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}

void dfs(int u, int marker) {
    if (ans[u]) return;
    ans[u] = marker;
    for (int i = head[u]; i; i = nxt[i])
        dfs(to[i], marker);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(v, u); // 反向建图
    }
    // 从大到小遍历结点
    for (int i = n; i >= 1; --i)
        dfs(i, i);
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    putchar('\n');
    return 0;
}

复杂度

时间复杂度 $O(n+m)$ ，反图、答案和栈的空间复杂度 $O(n+m)$ 。

总结

“每个起点能到达的最大目标”可以反转成“每个目标能覆盖哪些起点”。再按目标从大到小染色，就能一次确定所有答案。

目录

题意

思路

Python 知识

代码

复杂度

总结