图的遍历

题意

对有向图中的每个点 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;
}

STL 写法

上面的 main.cpp 用链式前向星（head / to / nxt 三个数组）手工存图。C++ 里还有更省事的做法：vector<vector<int>> 邻接表，一句 rg[v].push_back(u) 就是给点 v 挂上一条反向边，不用自己管下标和指针，代价只是多一层 vector 的间接访问。

染色过程本来写成递归最直观，但 $n$ 可以到 $10^5$ ，图退化成一条长链时递归层数太深会爆栈，所以这里用 stack<int> 显式模拟：弹出点 u，没被染过就写上当前的 marker，再把没染色的邻居压栈。外层依旧按编号从大到小枚举，每个点只会被染色一次，复杂度不变。

对应的 cppbook 章节：vector：能改变长度的数组、stack：最后放入，最先取出

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/**
 * 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-07-27 00:00
 * update_at: 2026-10-09 19:59
 */
// main-stl.cpp：P3916 图的遍历（STL 写法）。
// 核心是反向建图：原图的 u -> v，在反图里存成 v -> u。
// 然后按编号从大到小枚举“候选最大编号”，在反图上染色，
// 第一次被染到的点，它的答案就是当前这个编号。
// 代码分层：读入 / 染色 / 输出各一个函数，main 只按顺序调用；
// 反图和答案这些核心数据放全局，函数之间共享。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, m;                 // 点数、边数
vector<vector<int>> rg;  // rg[v]：反图中 v 能一步走到的所有点（即原图中能走到 v 的点）
vector<int> ans;         // ans[u]：从 u 出发能到达的最大编号，0 表示还没染色

// 读入 n、m 和 m 条边，顺便就把反图建好
void read_input() {
    cin >> n >> m;

    rg.assign(n + 1, vector<int>());
    ans.assign(n + 1, 0);
    for (ll i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        rg[v].push_back(u); // 反向建边：v 连回 u
    }
}

// 从 start 出发，在反图上把能走到的点都染成 marker
// 用显式栈代替递归，避免 n = 1e5 的长链把递归栈压爆
void color(int start, int marker) {
    stack<int> st;
    st.push(start);

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (ans[u] != 0) {
            continue; // 这个点被更大的编号先染过了，答案已经确定
        }
        ans[u] = marker;

        ll deg = rg[u].size();
        for (ll i = 0; i < deg; i++) {
            int v = rg[u][i];
            if (ans[v] == 0) {
                st.push(v);
            }
        }
    }
}

// 编号从大到小枚举，先被染到的答案最大
void solve() {
    for (ll marker = n; marker >= 1; marker--) {
        if (ans[marker] == 0) { // 还没确定答案，才需要从它开始染色
            color((int)marker, (int)marker);
        }
    }
}

// 按编号 1..n 输出每个点的答案
void output() {
    for (ll i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

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

    read_input();
    solve();
    output();

    return 0;
}

复杂度

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

总结

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

目录

题意

思路

Python 知识

代码

STL 写法

复杂度

总结