GESP 题解库 / 7 级题解 / [GESP202609 七级] 必经之路 · 第 23 / 24 题
GESP202609 七级 · P17459 · 困难

必经之路

正图、反图各搜一次定出"在路径上的点",再逐个试删:删掉它后还有没有起点能走到终点。

📊
n ≤ 1000,m ≤ 2000
点、边规模
🔢
k ≤ n
必经点个数
⚡
O(|R∩Q| × (n+m))
剪枝后的验证成本
🎯
可达性 + 试删
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

题目来源:[GESP202609 七级] 必经之路(洛谷 P17459)。

给定一张有 n 个结点、m 条边的有向图 G,结点编号 1 ~ n,第 i 条边从 uᵢ 指向 vᵢ。

G 中任一入度为 0 的结点可以作为合法起点,任一出度为 0 的结点可以作为合法终点。

如果 G 中所有可能的从合法起点到合法终点的路径都会经过结点 u,则称 u 是必经点。注意必经点可以是合法起点或合法终点。

输入格式:第一行两个正整数 n、m;接下来 m 行每行两个正整数 uᵢ、vᵢ。

输出格式:第一行一个整数 k,表示必经点数量;如果存在必经点,则第二行从小到大输出所有必经点的编号。

数据保证:至少有一个合法起点、至少有一个合法终点,至少存在一条从一个合法起点到一个合法终点的路径,且不存在孤立点(出度和入度都为 0 的点)。1 ≤ n ≤ 1000,1 ≤ m ≤ 2000;40% 的数据 n ≤ 100、m ≤ 200。

💡
人话翻译:把所有"起点 → 终点"的路线想象成若干种旅行方案。如果每一种方案都躲不开结点 u,那 u 就是必经点。
等价说法(实现起来最顺手):删掉 u 之后,还有没有任何一个起点能走到任何一个终点?如果一条路都走不通,那 u 当然就是必经点。
注意"经过"包含起点和终点本身,所以当全图只有 1 个合法起点时,这个起点自己也会是必经点。

🔍 关键词提取

有向图多源多汇可达性(BFS / DFS)删点验证候选集剪枝

已知条件

项目说明
输入第一行 n、m;随后 m 行 uᵢ vᵢ
输出第一行 k;k > 0 时第二行升序输出编号(k = 0 只输出一行 0)
数据范围1 ≤ n ≤ 1000,1 ≤ m ≤ 2000
合法起点入度 = 0 的结点(至少一个)
合法终点出度 = 0 的结点(至少一个)
图的性质无孤立点;至少存在一条起点 → 终点路径

需要解决的问题

02
思维导图
整理解题思路的全貌
🚦 删掉 u,还有路可走吗?
🧠 概念辨析
合法起点 = 入度 0 的点
合法终点 = 出度 0 的点
必经点 = 所有起点→终点路径都经过它
起点、终点自己也可以是必经点
🔁 三步做法
① 正图从所有起点 BFS,得到集合 R
② 反图从所有终点 BFS,得到集合 Q
③ 候选 = R ∩ Q,逐个"禁掉 u"再搜一遍
若再不能到达任何终点 → u 必经
✂️ 剪枝与代价
只有 R ∩ Q 里的点才可能必经
每次 BFS 是 O(n + m) ≤ 3000
候选最多 n = 1000 个
最坏总运算量 ≈ 3 × 10⁶
⚠️ 易错点
拿 Tarjan 割点硬套(有向图不成立)
只从"某一个"起点出发
禁点后忘了把 u 从起点集合里剔除
k = 0 时多输出了一行
03
样例手算推导
样例 1 与样例 2 的完整推演

🧮 样例 1:n = 8,m = 9,输出 2 / 4 5

先把题面的 9 条边和每个点的出入度整理出来,顺便定出合法起点与合法终点。

边号有向边边号有向边
11 → 366 → 7
22 → 376 → 8
33 → 482 → 4
44 → 595 → 7
55 → 6——
结点12345678
入度00221121
出度12112200
角色起点起点中间点中间点中间点中间点终点终点

题面列出的全部 9 条路径,逐条看"绕开了谁"

#路径经过 3?经过 4?经过 5?经过 6?
11 → 3 → 4 → 5 → 7✓✓✓✗
21 → 3 → 4 → 5 → 6 → 7✓✓✓✓
31 → 3 → 4 → 5 → 6 → 8✓✓✓✓
42 → 3 → 4 → 5 → 7✓✓✓✗
52 → 3 → 4 → 5 → 6 → 7✓✓✓✓
62 → 3 → 4 → 5 → 6 → 8✓✓✓✓
72 → 4 → 5 → 7✗✓✓✗
82 → 4 → 5 → 6 → 7✗✓✓✓
92 → 4 → 5 → 6 → 8✗✓✓✓

一眼就能看出:4 号、5 号在全部 9 条路径里都出现;而 3 号被第 7~9 条绕开、6 号被第 1、4、7 条绕开。

1
算出两个集合:R 与 Q

R = {1, 2} 能到达的点 = {1, 2, 3, 4, 5, 6, 7, 8}

Q = 能到达 {7, 8} 的点 = {1, 2, 3, 4, 5, 6, 7, 8}

候选 = R ∩ Q = {1, 2, 3, 4, 5, 6, 7, 8}

本题正好所有点都在候选里

候选 8 个,逐个试删

2
试删 4:一条路都走不通了

起点 1 的唯一出边是 1 → 3,到了 3 之后唯一出边 3 → 4 已被禁

起点 2 → 3 → 4、2 → 4 也全部被禁

两个起点都困死,到不了 7、8 中任何一个

✅ 4 是必经点

3
试删 5:走到 4 就断了

1 → 3 → 4 后,4 的唯一出边 4 → 5 被禁

2 → 4 也同样被卡在 4

没有任何起点能到达终点 7 或 8

✅ 5 是必经点

4
试删 6:还有 5 → 7 这条捷径

1 → 3 → 4 → 5 → 7(边 5 → 7 存在,不需要经过 6)

终点 7 依然可达

❌ 6 不是必经点

5
试删 7:还能到 8

1 → 3 → 4 → 5 → 6 → 8

终点 8 依然可达

❌ 7 不是必经点

6
试删 1 或 2:另一个起点顶上

删 1 时:从 2 出发仍能到达 7、8

删 2 时:从 1 出发仍能到达 7、8

❌ 1、2 都不是

k = 2,编号 4 5 ✓

🔑
3 号点为什么被"冤枉"了?它在 9 条路径中的 6 条里出现,看起来很像枢纽,但第 7~9 条 2 → 4 → 5 → … 恰好不需要它。
这就是"所有路径都经过"与"大多数路径经过"的区别——判定时必须严格到"一条漏网都不行"。

🧮 样例 2:只改两条边,答案就变成 0

样例 2 把 2 → 4 换成了 2 → 5,把 5 → 7 换成了 4 → 7。这两条"抄近道"的边,正好各自破坏了原来两个必经点的必要性。

边怎么改原来的作用改完之后的效果
2 → 4 改成 2 → 52 号必须借道 3、4 才能往下走2 号可以绕过 3 和 4,直接进 5
5 → 7 改成 4 → 75 号是通往终点 7 的必经一步4 号可以绕过 5 和 6,直接进 7
1
试删 4:2 号抄近道绕开了它

从 2 出发:2 → 5 → 6 → 7

通往 7 与 8 的路都还在

❌ 4 不再是必经点

2
试删 5:1 号抄近道绕开了它

从 1 出发:1 → 3 → 4 → 7(新边 4 → 7)

根本不需要经过 5、6

❌ 5 不再是必经点

3
其余点也都有"替代路线"

删 6:1 → 3 → 4 → 7 绕过;删 3:2 → 5 → 6 → 8 绕过

删 1:从 2 出发有路;删 2:从 1 出发有路

删 7:还能到 8;删 8:还能到 7

❌ 全部候选都不是必经点

k = 0,只输出一行 0 ✓

⚠️
k = 0 的输出格式要小心:此时只输出一行 0,第二行不要打印(也不要打印空行)。有些写法把第二行留空,结果多出一个换行,严格比对的评测就会判错。
正确写法:先输出 k,再判断 if (k > 0) 才输出第二行。
04
解法对比
可达性 + 试删 vs 枚举所有路径 / Tarjan 割点

⚔️ 解法对比

🟢 可达性 + 试删(推荐) 推荐

正图从起点搜出 R、反图从终点搜出 Q,候选 = R ∩ Q,再逐个禁点验证

  • 候选最坏 n = 1000 个,每个一次 BFS O(n + m)
  • 总运算量 ≤ 3 × 10⁶,1 秒绰绰有余
  • 代码约 60 行,只有"搜两遍 + 试删"三个动作
  • 正确性由"路径不过 u ⟺ 删掉 u 后仍可达"直接保证
💡
两遍 BFS 就能定出候选的原因:R 是"起点能碰到的点",Q 是"能碰到终点的点",两者相交恰好是"落在某条起点→终点路径上的点"。必经点一定落在路径上,所以候选之外的点根本不用试。

🟠 枚举所有路径

用 DFS 把所有起点→终点的路径列出来,再取点集的交集

  • 路径条数指数级增长
  • m = 2000 时完全不可行
  • 代码看起来很短
  • 规模上直接出局
⚠️
反例感受一下:只要造 20 层"左右二选一"的菱形结构,路径就有 2²⁰ ≈ 10⁶ 条,再多几层就彻底爆炸。所以绝不能枚举路径,只能用"搜索判断存在性"。

📈 性能对比

方案复杂度代码量
可达性 + 试删(正解)O(|R ∩ Q| × (n + m)) ≤ 3 × 10⁶约 60 行
枚举所有路径指数级❌ 不可行
Tarjan 求割点O(n + m)❌ 定义不适用于有向图 + 多源多汇
05
算法流程图
两遍 BFS 定候选,再逐个禁点验证
开始读入 n、m 与 m 条有向边,统计每个点的入度、出度,并建好反图合法起点 = 入度 0 的点;合法终点 = 出度 0 的点正图从所有起点 BFS,得到可达集合 R反图从所有终点 BFS,得到"能到终点"的集合 Q候选集合 = R ∩ Q(必经点必在其中)逐个取候选点 u 做试删禁掉 u 后,从其余起点出发还能到达某个终点吗不能 ✗u 是必经点,记入答案能 ✓u 不是必经点,跳过先输出答案个数 k;若 k > 0 再升序输出所有编号试下一个候选点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🚦 必经点判定器

第一行输入 n、m,随后 m 行每行一条有向边 u v。程序会算出合法起点/终点、候选集合,并逐个试删给出必经点。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(正反图可达性 + 逐个试删)

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

int n, m;
vector<int> g[1005], rg[1005];        // 正图 / 反图
int indeg[1005], outdeg[1005];
vector<int> st, en;                   // 合法起点 / 合法终点
bool vis[1005];

// 从 srcs 出发做 BFS;rev = true 表示走反图;ban 表示禁止经过的点(0 表示不禁止)
void bfs(const vector<int> &srcs, bool rev, int ban) {
    fill(vis + 1, vis + n + 1, false);
    static int q[1005];
    int head = 0, tail = 0;
    for (int s : srcs) {
        if (s == ban || vis[s]) continue;     // 被禁的点既不能出发,也不能被访问
        vis[s] = true;
        q[tail++] = s;
    }
    while (head < tail) {
        int u = q[head++];
        const vector<int> &adj = rev ? rg[u] : g[u];
        for (int v : adj) {
            if (v == ban || vis[v]) continue;
            vis[v] = true;
            q[tail++] = v;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        rg[v].push_back(u);               // 反图:v 的反向邻居是 u
        outdeg[u]++;
        indeg[v]++;
    }

    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0)  st.push_back(i);   // 合法起点
        if (outdeg[i] == 0) en.push_back(i);   // 合法终点
    }

    bool R[1005], Q[1005];
    bfs(st, false, 0);
    for (int i = 1; i <= n; i++) R[i] = vis[i];    // R:起点能到达的点

    bfs(en, true, 0);
    for (int i = 1; i <= n; i++) Q[i] = vis[i];    // Q:能到达某个终点的点

    vector<int> ans;
    for (int u = 1; u <= n; u++) {
        if (!R[u] || !Q[u]) continue;              // 剪枝:不在任何起点→终点路径上
        bfs(st, false, u);                         // 禁掉 u 再走一遍
        bool survive = false;
        for (int e : en)
            if (e != u && vis[e]) { survive = true; break; }
        if (!survive) ans.push_back(u);             // 一条路都不剩 → u 是必经点
    }

    printf("%d\n", (int)ans.size());               // 注意:k = 0 时只有这一行
    for (int i = 0; i < (int)ans.size(); i++)
        printf("%d%c", ans[i], i + 1 == (int)ans.size() ? '\n' : ' ');
    return 0;
}
🔑
三处细节决定成败:① 起点集合里要跳过被禁的 u,否则"从 u 出发"会被当成有路可走;② 判定时必须排除 e == u,因为 u 自己可能正好是出度为 0 的合法终点;③ k = 0 时只输出第一行。

📖 关键几行怎么看

代码作用为什么这样写
if (indeg[i] == 0) st.push_back(i)合法起点入度 0 才能当起点;出度 0 当终点
rg[v].push_back(u)建反图"谁能到终点"要在反图上从终点出发搜
bfs(st, false, 0)求 R正图、不禁点:得到"起点能碰到的点"
bfs(en, true, 0)求 Q反图、从终点出发:得到"能碰到终点的点"
if (!R[u] || !Q[u]) continue;剪枝候选只保留 R ∩ Q,其余点不可能是必经点
bfs(st, false, u)试删把 u 同时设为"禁止经过"和"禁止出发"
if (e != u && vis[e])判定u 自己可能就是终点,要排除,否则永远判不出必经点
⚠️
五个坑:① 只从某一个起点出发(起点可能有多个,必须全部作为源);② 忘记建反图,没法算 Q;③ 试删时还让 u 参与出发;④ 判定可达时没排除 e == u;⑤ 把 Tarjan 割点模板硬套上来(有向图 + 多源多汇,定义都不成立)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
8 9
1 3
2 3
3 4
4 5
5 6
6 7
6 8
2 4
5 7
2
4 5
题面样例 1
8 9
1 3
2 3
3 4
4 5
5 6
6 7
6 8
2 5
4 7
0题面样例 2:两条"抄近道"的边让必经点消失
3 2
1 2
2 3
3
1 2 3
单链:起点、中间点、终点全是必经点
5 5
1 2
1 3
2 4
3 4
4 5
3
1 4 5
两条并联支路:2、3 可绕,1、4、5 躲不开
2 1
1 2
2
1 2
最小图:唯一入度 0 与唯一出度 0 都是必经点
4 3
1 2
2 3
2 4
2
1 2
两个合法终点(3、4):1、2 是必经点
5 4
1 3
2 3
4 3
3 5
2
3 5
三个合法起点汇到 3:3、5 是必经点
✅
自查清单:① 起点集合是否包含全部入度 0 的点?② 是否正图、反图各搜了一遍?③ 候选是不是 R ∩ Q?④ 试删 u 时是否把 u 从起点集合里剔除了?⑤ 判定时是否排除了 e == u?⑥ 输出格式对不对(先 k,k > 0 才有第二行)?

🚨 易错点清单

⚠️
多源多汇要搜全:起点可能不止一个,必须把所有入度为 0 的点都放进 BFS 的起点集合;只从一个起点出发会漏判。
⚠️
别用 Tarjan 割点:割点是无向图连通性概念,本题是有向图且多源多汇,"连通"不成立,必须用"删掉 u 后起点还能不能到终点"来判定。
⚠️
试删时要把 u 从起点集合剔除:如果 u 本身是合法起点,却还让 BFS 从它出发,就会得到"有路可走"的错误结论。
⚠️
判定终点时排除 e == u:u 自己可能就是出度为 0 的合法终点,不排除的话每个候选都会被判成"还有路可走"。
⚠️
k = 0 的输出:只输出一行 0,第二行绝不能打印(哪怕空行也不行)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(|R∩Q| × (n + m))
空间复杂度
O(n + m)
n, m 上限
1000 / 2000
最坏运算量
约 3 × 10⁶

时间怎么算的?

空间都用在哪?

邻接表正反两份共 2 × (n + m) 条边、以及若干长度为 n 的数组,空间只要几百 KB。

✅ 约 300 万次操作,稳稳通过。剪枝(只在 R ∩ Q 上验证)虽然不改变最坏复杂度,但它是"必经点必在路径上"这一结论的自然产物,常数更小、思路也更清晰。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ① 正反图可达性:图上"两侧夹逼"的通用套路
bfs(st, false, 0);        // R:起点能碰到谁
bfs(en, true,  0);        // Q:谁能碰到终点
// 落在"起点→终点"路径上的点 = R ∩ Q

// ② 多源 BFS 的写法:起点集合一次性全部入队
int head = 0, tail = 0;
for (int s : srcs) { if (!vis[s]) { vis[s] = true; q[tail++] = s; } }
while (head < tail) { /* 扩展邻接点 */ }

// ③ "删点验证"的写法:把被禁点同时挡在"出发"和"入队"两处
for (int s : srcs) { if (s == ban || vis[s]) continue; vis[s] = true; q[tail++] = s; }
if (v == ban || vis[v]) continue;      // 扩展时也要挡

// ④ 多源多汇:起点 = 入度 0,终点 = 出度 0
if (indeg[i] == 0) st.push_back(i);
if (outdeg[i] == 0) en.push_back(i);

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
正反图可达性用两次 BFS 分别求出"起点侧"和"终点侧"支配点、关键边、路径计数等图上结构题
多源 BFS起点集合一次性全部入队超级源点、多起点最短路、网络流源汇处理
删点 / 删边验证把候选禁掉后再搜一次,看还剩不剩下目标割点 / 割边、桥、关键结点的判定
候选集剪枝只在 R ∩ Q 上做验证所有"先缩小候选再暴力验证"的题
输出格式控制k = 0 时只输出一行所有"多行输出且有条件分支"的题
🌟
思考题:如果把问题换成"删掉 k 个点之后仍然保证有路可走,最少需要删哪几个点",或者"删除后最短路长度会变长的点有哪些",该怎么做?(提示:前者已经接近"支配集 / 支配树"问题;后者需要对每个点比较删前删后的最短路,复杂度 O(n × (m log n)),n = 1000 时约 2 × 10⁷,仍然可行。
本题只用到了"存在性",换一种问法就要换一套算法——看清问的是"有没有"还是"是多少",是图论题的关键分水岭。)