P3916 图的遍历 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P3916，日期见页头。两边不一致时信原站。

题目描述

给出 N 个点，M 条边的有向图，对于每个点 v，令 A(v) 表示从点 v 出发，能到达的编号最大的点。现在请求出 A(1), A(2), …, A(N) 的值。

输入格式

第 1 行 2 个整数 N, M，表示点数和边数。

接下来 M 行，每行 2 个整数 Uᵢ, Vᵢ，表示边 (Uᵢ, Vᵢ)。点用 1, 2, …, N 编号。

输出格式

一行 N 个整数 A(1), A(2), …, A(N)。

说明/提示

对于 60% 的数据，1 ≤ N, M ≤ 10³。
对于 100% 的数据，1 ≤ N, M ≤ 10⁵。

输入输出样例

输入

输出

4 4 3 4

1 → 2 → 4 → 3。所以 A(1) = A(2) = A(4) = 4；而 4 号点只能走到 3，A(4) 仍是 4（自己也算）； 3 号点没有出边，A(3) = 3。

1★ 第一版：对每个点各搜一遍 —— 答案永远对，而它拿 60 分

p3916Brute.cpp⚠ 每个点各搜一遍：O(N(N+M))

// ⚠ P3916 第一版：**对每个点各跑一次 DFS** —— 答案永远是对的，可它跑不完。
//
// 「从点 v 出发能到达的编号最大的点」—— 最直接的读法就是：
// 对每个 v 从头搜一遍，路上见过的编号取 max。写出来五分钟，一个字都不难。
//
// 复杂度 O(N(N + M))。题面 N, M ≤ 10⁵ ⇒ 顶格约 **10¹⁰** 次，一秒钟必挂。
//
// ★★ 但**别急着删它**，题面里写着：「对于 60% 的数据，1 ≤ N, M ≤ 10³」——
//   那一档它只要 2 × 10⁶ 次，**稳稳拿 60 分**。
//   ⇒ 出题人把「暴力值多少分」直接写在数据范围里了（[第 24 章 P1776](/sol/p1776/) 同款）。
//
// ★ 它同时是本页的**对拍参照物**：和正解的思路完全无关（一个正着搜、一个反着搜）。
//
// ⚠ 命令行给一个 `count` 参数，它就只打「一共走了多少条边」，用来和正解比次数。

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

int n, m;
vector<vector<int>> g;
vector<char> vis;
long long steps = 0;

int main(int argc, char** argv) {
    bool countOnly = (argc > 1 && string(argv[1]) == "count");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    string out;
    vector<int> st;
    for (int s = 1; s <= n; s++) {
        vis.assign(n + 1, 0);                         // ★ 每个起点都要从头再来
        int best = s;
        st.clear();
        st.push_back(s);
        vis[s] = 1;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            best = max(best, u);
            for (int v : g[u]) {
                steps++;
                if (!vis[v]) { vis[v] = 1; st.push_back(v); }
            }
        }
        out += to_string(best);
        out += (s == n ? '\n' : ' ');
    }
    if (countOnly) { printf("%lld\n", steps); return 0; }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 题面那句「对于 60% 的数据 N, M ≤ 10³」就是出题人替暴力写好的一档

N(N + M)：顶格 10⁵ 是 2 × 10¹⁰ 次，而 60% 那一档只有 2 × 10⁶ 次。

实测那一档（N = M = 10³ 随机）暴力只走了 16 942 条边 —— 稳拿 60 分。 ⇒ 这是本轮那条主线的又一次现场：第 24 章、第 23 章都量过 ——数据范围那几行不是背景，每一行都是一件工具。 ⚠ 所以哪怕想不出正解，这一版也必须写出来交上去。

2★★ 正解：把问题反过来问 —— 反向建图，从编号最大的点开始

与其问「v 能到达谁」，不如问「谁能到达 n」—— 那些点的答案全是 n（它是最大编号）。而「谁能到达 n」在反向图上就是「从 n 出发能走到谁」。

    建反向图（原图 u → v 就存 v → u）
    for (int s = n; s >= 1; s--)
        if (还没定过 s 的答案) 从 s 出发在反图上 DFS，
                              一路碰到的点答案全填 s

p3916.cpp★★ 反向图 + 从大到小，O(N+M)

// ★★ P3916 正解：**反向建图**，从编号最大的点开始倒着搜，一遍搞定。
//
// 换个问法：与其问「v 能到达谁」，不如问「**谁能到达 n**」——
// 那些点的答案全是 n（n 是最大编号）。而「谁能到达 n」在**反向图**上就是「从 n 出发能走到谁」。
//
//     建反向图（原图 u → v 就存 v → u）
//     for (int s = n; s >= 1; s--)
//         if (!vis[s]) dfs(s);          // 这一趟碰到的点，答案全是 s
//
// ★★★ 为什么「已经标记过的点就不用再走」是对的（这一步不证清楚就只是碰运气）：
//   设点 u 在处理起点 v 时被标记（⇒ A(u) = v），现在处理更小的起点 s < v，
//   走到了 u。反向图上从 u 还能走到 w，意味着**原图里 w 能到 u**；
//   而 u 能到 v ⇒ **w 也能到 v** ⇒ w 在处理 v 那一趟就已经被标记过了。
//   ⇒ **停在 u 不会漏掉任何点。**
//
// 复杂度 O(N + M) —— 每条反向边只被走一次。顶格 10⁵ + 10⁵。
//
// ⚠ DFS 写成迭代的：顶格 10⁵ 排成一条链时递归会爆栈（[P5318](/sol/p5318/) 第 ⑥ 步量过）。
// ⚠ 命令行给一个 `count` 参数，它就只打「一共走了多少条边」。

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

int main(int argc, char** argv) {
    bool countOnly = (argc > 1 && string(argv[1]) == "count");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> rg(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        rg[v].push_back(u);                           // ★ 反着存
    }

    vector<int> a(n + 1, 0), st;
    long long steps = 0;
    for (int s = n; s >= 1; s--) {                    // ★ 从大到小
        if (a[s]) continue;
        st.clear();
        st.push_back(s);
        a[s] = s;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            for (int v : rg[u]) {
                steps++;
                if (!a[v]) { a[v] = s; st.push_back(v); }
            }
        }
    }
    if (countOnly) { printf("%lld\n", steps); return 0; }

    string out;
    for (int i = 1; i <= n; i++) { out += to_string(a[i]); out += (i == n ? '\n' : ' '); }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 「已经填过的点就不用再走」为什么不会漏 —— 这一步不证清楚就只是碰运气

设点 u 在处理起点 v 时被填上（A(u) = v），现在处理更小的起点 s < v，走到了 u。反向图上从 u 还能走到 w，意味着原图里 w 能到 u；而 u 能到 v ⇒ w 也能到 v ⇒ w 在处理 v 那一趟就已经被填过了。

⇒ 停在 u 不会漏掉任何点。 每条反向边一辈子只被走一次 ⇒ O(N + M)。

⚠ 而这个证明离不开「从大到小」这三个字：它保证「先填上的一定是更大的答案」。下一步就是把这三个字拿掉看看。

3⚠ 两个错法，各配一条精确的恒等式 —— 说清楚它「算了什么」

p3916Fwd.cpp✗ 忘了反向建图（样例挡得住）

// ✗ P3916 错法一：**忘了反向建图** —— 照原图存，还是从 n 到 1 倒着搜。
//
// 这一版把「谁能到达 n」错读成了「n 能到达谁」。两句话在有向图上完全不是一回事，
// 而在**无向图**上它们是一回事 —— 这就是这个 bug 的来处：
// 上一道 [B3643](/sol/b3643/) 存的是无向图，一条边存两遍；到这道题**只能存一遍，而且方向要反过来**。
//
// ⇒ ★★ 又一次「[上一道题的正确写法就是这一道题的 bug](/sol/p1171/)」。

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);                            // ★ 没反过来
    }

    vector<int> a(n + 1, 0), st;
    for (int s = n; s >= 1; s--) {
        if (a[s]) continue;
        st.clear(); st.push_back(s); a[s] = s;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            for (int v : g[u]) if (!a[v]) { a[v] = s; st.push_back(v); }
        }
    }
    string out;
    for (int i = 1; i <= n; i++) { out += to_string(a[i]); out += (i == n ? '\n' : ' '); }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p3916Asc.cpp✗ 起点从小到大（样例挡得住）

// ✗ P3916 错法二：反向图建对了，可**起点从小到大枚举**。
//
// 「从大到小」这三个字是整个算法的支点：先处理大的编号，
// 才能保证「一个点第一次被碰到时，碰它的那个起点就是它能到达的最大编号」。
// 倒过来枚举，每个点会被**最小的能到它的编号**先抢走。
//
// ★ 说清楚它算了什么：它求的是「从 v 出发能到达的编号**最小**的点」。

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> rg(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        rg[v].push_back(u);
    }

    vector<int> a(n + 1, 0), st;
    for (int s = 1; s <= n; s++) {                    // ★ 顺序反了
        if (a[s]) continue;
        st.clear(); st.push_back(s); a[s] = s;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            for (int v : rg[u]) if (!a[v]) { a[v] = s; st.push_back(v); }
        }
    }
    string out;
    for (int i = 1; i <= n; i++) { out += to_string(a[i]); out += (i == n ? '\n' : ' '); }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 与其说「它错了」，不如说清「它算的是另一个量」

错法	它其实算的是	300 轮逐个相等
起点从小到大	从 `v` 出发能到达的编号最小的点	★ 300 / 300
忘了反向建图	在反图上跑正解 = 「能到达 `v` 的最大编号」	★ 300 / 300

⇒ 说清楚之后，「什么时候它会蒙对」就是白送的推论 —— 而且量得出来。把每条边都存两遍（图变成对称的，原图 = 反图）：

300 轮	照题面（有向）	对称化（每条边双向）
忘了反向建图	282	★ 精确的 0
起点从小到大	293	293

★★ 同一档数据，两个错法命运相反 —— 因为它们坏的根本不是同一样东西：一个坏在「边的方向」上（对称化之后方向就没意义了），一个坏在「枚举顺序」上（和方向无关）。

★ 顺带又一次「上一道题的正确写法就是这一道题的 bug」：

B3643 存的是无向图，一条边要存两遍；这道题只能存一遍，而且方向要反过来。

4★★★ 第三个「错法」答案一个字都不错 —— 样例和对拍一起失灵

把正解里那句「已经填过的点就别再走了」删掉（每个起点都把标记清空重来）：

p3916Clear.cpp⚠ 答案全对，只是退回 O(N(N+M))

// ⚠ P3916 错法三：反向图、从大到小都对，**可每个起点都把标记清空重来**。
//
// 也就是把那句「已经算过的点就别再走了」删掉。
// **答案一个字都不会错** —— 对拍跑多少轮都是 0 次不一致。
// 它坏掉的只有复杂度：从 O(N + M) 退回 O(N(N + M))，顶格 10¹⁰。
//
// ★★ 这就是[第 20 章 P5019](/sol/p5019/) 那条的又一次现场：
//   **官方样例和对拍这两个过滤器，筛的都是「答案错」，对「答案对但跑不完」完全无能为力。**
//   ⇒ 只能**数次数** —— 解析页第 ⑥ 步那张表就是这么来的。
//
// ⚠ 命令行给一个 `count` 参数，它就只打「一共走了多少条边」。

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

int main(int argc, char** argv) {
    bool countOnly = (argc > 1 && string(argv[1]) == "count");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> rg(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        rg[v].push_back(u);
    }

    vector<int> a(n + 1, 0), st;
    long long steps = 0;
    for (int s = n; s >= 1; s--) {
        vector<char> vis(n + 1, 0);                   // ★ 每个起点都从头再来
        st.clear(); st.push_back(s); vis[s] = 1;
        if (!a[s]) a[s] = s;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            if (!a[u]) a[u] = s;
            for (int v : rg[u]) {
                steps++;
                if (!vis[v]) { vis[v] = 1; st.push_back(v); }
            }
        }
    }
    if (countOnly) { printf("%lld\n", steps); return 0; }
    string out;
    for (int i = 1; i <= n; i++) { out += to_string(a[i]); out += (i == n ? '\n' : ' '); }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 官方样例和对拍这两个过滤器，筛的都是「答案错」


官方样例挡住它了吗	★ 没有（原样打出 `4 4 3 4`）
300 轮对拍抓到几次	★ 精确的 0（答案根本没错）

⇒ 只能数次数。造一条链 1 → 2 → … → n（正解在这上面只走 n−1 条边）：

一条链	正解走的边	每次清空标记	倍数
`n = 1000`	999	499 500	500.0
`n = 2000`	1999	1 999 000	1000.0
`n = 4000`	3999	7 998 000	2000.0

★★ 关键不是那三个数，是倍数在往上走（n 翻一倍，倍数就翻一倍）—— 这就是 O(n²) 的签名。和第 20 章 P5019 那次一模一样： 「答案对但跑不完」只能靠数次数＋造对形状发现。

5⚠⚠ 而「造对形状」这四个字在这道题上特别值钱：顶格随机数据是过得去的

顶格 N = M = 10⁵（A 机 · WSL2 · i5-13500H · 2026-08-30，独占，时限 1 秒）：

顶格数据的形状	暴力走的边	暴力耗时	正解走的边	正解耗时
随机（`M` 条边随便连）	5 238 929	★ 0.23 秒	100 000	0.01 秒
★ 一条链 `1 → 2 → … → 10⁵`	4 999 950 000	★ 36.35 秒	99 999	0.01 秒

★★★ 同样是「顶格」，两种形状差 150 倍 —— 一个过一个挂

随机稀疏有向图里，每个点能到达的点很少（平均出度只有 1），于是那个 O(N(N+M)) 的暴力在顶格随机数据上照样 0.23 秒跑完。

⇒ 这是第 51 章那条「造一组大数据跑一次也不够 —— 要造对形状」的又一次现场，也和第 4 章 P1731 的「『数据范围顶格』不等于『最坏』」是同一件事。 ★ 顺手随机一组顶格数据然后说『能过』，是这本书里被打脸次数最多的动作之一。

6★ 对拍这一页（参照物就是第 ① 版）

300 轮（`n` 随机 3~10 的随机有向图）
正解 ≡ 暴力	★ 不一致 0 轮
忘了反向建图	282
起点从小到大	293
⚠ 每个起点都清空标记	★ 0（答案根本没错）

顶格的两个数：正解 O(N + M) = 2 × 10⁵；暴力 O(N(N + M)) = 2 × 10¹⁰ —— 差 10 万倍。

7度量程序和生成器

p3916Count.cpp度量程序（本页所有数字都出自它）

p3916Gen.cpp数据生成器

8一页纸


★★ 关键的一步	把「v 能到谁」反过来问成「谁能到 n」⇒ 反向建图 + 从大到小
★ 剪枝为什么不漏	走到已填的 `u` ⇒ 它后面的点在填 `u` 那一趟就填过了（两行能证）
★★ 第一版值多少	`O(N(N+M))`，题面 60% 档 `N,M ≤ 10³` 就是替它写的 ⇒ 稳拿 60 分
★★ 两个错法算了什么	顺序反了 ≡ 最小编号（300/300）；忘了反向 ≡ 在反图上跑正解（300/300）
★★★ 第三个不改答案	删掉记忆化 ⇒ 样例放过、对拍精确的 0，只能数次数（倍数 500 → 1000 → 2000）
★★★ 顶格 ≠ 最坏	顶格随机 0.23 秒就过了，顶格一条链 36.35 秒 —— 差 150 倍

洛谷 P3916 图的遍历

0题目原文（本地存了一份）

输入

输出

1★ 第一版：对每个点各搜一遍 —— 答案永远对，而它拿 60 分

2★★ 正解：把问题反过来问 —— 反向建图，从编号最大的点开始

3⚠ 两个错法，各配一条精确的恒等式 —— 说清楚它「算了什么」

4★★★ 第三个「错法」答案一个字都不错 —— 样例和对拍一起失灵

5⚠⚠ 而「造对形状」这四个字在这道题上特别值钱：顶格随机数据是过得去的

6★ 对拍这一页（参照物就是第 ① 版）

7度量程序和生成器

8一页纸