正图、反图各搜一次定出"在路径上的点",再逐个试删:删掉它后还有没有起点能走到终点。
题目来源:[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。
有向图多源多汇可达性(BFS / DFS)删点验证候选集剪枝
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 m 行 uᵢ vᵢ |
| 输出 | 第一行 k;k > 0 时第二行升序输出编号(k = 0 只输出一行 0) |
| 数据范围 | 1 ≤ n ≤ 1000,1 ≤ m ≤ 2000 |
| 合法起点 | 入度 = 0 的结点(至少一个) |
| 合法终点 | 出度 = 0 的结点(至少一个) |
| 图的性质 | 无孤立点;至少存在一条起点 → 终点路径 |
R ∩ Q?设 R = 所有起点能到达的点集合,Q = 所有能到达某个终点的点集合;一个点"落在某条起点→终点路径上" ⟺ 起点能到它,且它能到终点。必经点必然在某条路径上(题目保证至少有一条路径),所以只需在 R ∩ Q 里逐个验证先把题面的 9 条边和每个点的出入度整理出来,顺便定出合法起点与合法终点。
| 边号 | 有向边 | 边号 | 有向边 |
|---|---|---|---|
| 1 | 1 → 3 | 6 | 6 → 7 |
| 2 | 2 → 3 | 7 | 6 → 8 |
| 3 | 3 → 4 | 8 | 2 → 4 |
| 4 | 4 → 5 | 9 | 5 → 7 |
| 5 | 5 → 6 | — | — |
| 结点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 入度 | 0 | 0 | 2 | 2 | 1 | 1 | 2 | 1 |
| 出度 | 1 | 2 | 1 | 1 | 2 | 2 | 0 | 0 |
| 角色 | 起点 | 起点 | 中间点 | 中间点 | 中间点 | 中间点 | 终点 | 终点 |
| # | 路径 | 经过 3? | 经过 4? | 经过 5? | 经过 6? |
|---|---|---|---|---|---|
| 1 | 1 → 3 → 4 → 5 → 7 | ✓ | ✓ | ✓ | ✗ |
| 2 | 1 → 3 → 4 → 5 → 6 → 7 | ✓ | ✓ | ✓ | ✓ |
| 3 | 1 → 3 → 4 → 5 → 6 → 8 | ✓ | ✓ | ✓ | ✓ |
| 4 | 2 → 3 → 4 → 5 → 7 | ✓ | ✓ | ✓ | ✗ |
| 5 | 2 → 3 → 4 → 5 → 6 → 7 | ✓ | ✓ | ✓ | ✓ |
| 6 | 2 → 3 → 4 → 5 → 6 → 8 | ✓ | ✓ | ✓ | ✓ |
| 7 | 2 → 4 → 5 → 7 | ✗ | ✓ | ✓ | ✗ |
| 8 | 2 → 4 → 5 → 6 → 7 | ✗ | ✓ | ✓ | ✓ |
| 9 | 2 → 4 → 5 → 6 → 8 | ✗ | ✓ | ✓ | ✓ |
一眼就能看出:4 号、5 号在全部 9 条路径里都出现;而 3 号被第 7~9 条绕开、6 号被第 1、4、7 条绕开。
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 个,逐个试删
起点 1 的唯一出边是 1 → 3,到了 3 之后唯一出边 3 → 4 已被禁
起点 2 → 3 → 4、2 → 4 也全部被禁
两个起点都困死,到不了 7、8 中任何一个
✅ 4 是必经点
1 → 3 → 4 后,4 的唯一出边 4 → 5 被禁
2 → 4 也同样被卡在 4
没有任何起点能到达终点 7 或 8
✅ 5 是必经点
1 → 3 → 4 → 5 → 7(边 5 → 7 存在,不需要经过 6)
终点 7 依然可达
❌ 6 不是必经点
1 → 3 → 4 → 5 → 6 → 8
终点 8 依然可达
❌ 7 不是必经点
删 1 时:从 2 出发仍能到达 7、8
删 2 时:从 1 出发仍能到达 7、8
❌ 1、2 都不是
k = 2,编号 4 5 ✓
2 → 4 → 5 → … 恰好不需要它。样例 2 把 2 → 4 换成了 2 → 5,把 5 → 7 换成了 4 → 7。这两条"抄近道"的边,正好各自破坏了原来两个必经点的必要性。
| 边怎么改 | 原来的作用 | 改完之后的效果 |
|---|---|---|
| 2 → 4 改成 2 → 5 | 2 号必须借道 3、4 才能往下走 | 2 号可以绕过 3 和 4,直接进 5 |
| 5 → 7 改成 4 → 7 | 5 号是通往终点 7 的必经一步 | 4 号可以绕过 5 和 6,直接进 7 |
从 2 出发:2 → 5 → 6 → 7
通往 7 与 8 的路都还在
❌ 4 不再是必经点
从 1 出发:1 → 3 → 4 → 7(新边 4 → 7)
根本不需要经过 5、6
❌ 5 不再是必经点
删 6:1 → 3 → 4 → 7 绕过;删 3:2 → 5 → 6 → 8 绕过
删 1:从 2 出发有路;删 2:从 1 出发有路
删 7:还能到 8;删 8:还能到 7
❌ 全部候选都不是必经点
k = 0,只输出一行 0 ✓
0,第二行不要打印(也不要打印空行)。有些写法把第二行留空,结果多出一个换行,严格比对的评测就会判错。if (k > 0) 才输出第二行。正图从起点搜出 R、反图从终点搜出 Q,候选 = R ∩ Q,再逐个禁点验证
用 DFS 把所有起点→终点的路径列出来,再取点集的交集
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 可达性 + 试删(正解) | O(|R ∩ Q| × (n + m)) ≤ 3 × 10⁶ | 约 60 行 |
| 枚举所有路径 | 指数级 | ❌ 不可行 |
| Tarjan 求割点 | O(n + m) | ❌ 定义不适用于有向图 + 多源多汇 |
第一行输入 n、m,随后 m 行每行一条有向边 u v。程序会算出合法起点/终点、候选集合,并逐个试删给出必经点。
点按钮开始 →
#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 自己可能就是终点,要排除,否则永远判不出必经点 |
u 参与出发;④ 判定可达时没排除 e == u;⑤ 把 Tarjan 割点模板硬套上来(有向图 + 多源多汇,定义都不成立)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
8 9 | 2 4 5 | 题面样例 1 |
8 9 | 0 | 题面样例 2:两条"抄近道"的边让必经点消失 |
3 2 | 3 1 2 3 | 单链:起点、中间点、终点全是必经点 |
5 5 | 3 1 4 5 | 两条并联支路:2、3 可绕,1、4、5 躲不开 |
2 1 | 2 1 2 | 最小图:唯一入度 0 与唯一出度 0 都是必经点 |
4 3 | 2 1 2 | 两个合法终点(3、4):1、2 是必经点 |
5 4 | 2 3 5 | 三个合法起点汇到 3:3、5 是必经点 |
R ∩ Q?④ 试删 u 时是否把 u 从起点集合里剔除了?⑤ 判定时是否排除了 e == u?⑥ 输出格式对不对(先 k,k > 0 才有第二行)?0,第二行绝不能打印(哪怕空行也不行)。邻接表正反两份共 2 × (n + m) 条边、以及若干长度为 n 的数组,空间只要几百 KB。
✅ 约 300 万次操作,稳稳通过。剪枝(只在 R ∩ Q 上验证)虽然不改变最坏复杂度,但它是"必经点必在路径上"这一结论的自然产物,常数更小、思路也更清晰。
// ① 正反图可达性:图上"两侧夹逼"的通用套路 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 时只输出一行 | 所有"多行输出且有条件分支"的题 |