有向图上对每个起点各跑一次 BFS 预处理全源可达矩阵,此后每次询问 O(1) 查表回答 Yes/No。
OJ: roj
题目 ID: 2123
难度:普及-
标签:图论BFS传递闭包python
创建: 2026-10-08 07:33
更新: 2026-10-08 07:33
形式化题目
给定一个有向图
即从 Yes,否则输出 No,共
约束:
数据说明:本题题面与测试数据均由仓库内的生成脚本自造(素材源带
data.py), 并非官方原始数据;题面本身的来源是「信息学奥赛一本通 · 数据结构基础 · 第四章 图论算法」。 生成脚本取(与 、 同量级,属于工作范围而非题面声明), 并刻意包含自环、重边、长链与强连通环;对 的询问只在与「路径长度 」 的读法结论一致时才出现,因此数据不依赖「长度 算不算可达」这处语义选择。
正解
思路
朴素做法。 每次询问现场搜索一遍:从 Yes,
搜完整张图都没碰到就输出 No。单次代价
瓶颈在哪? 瓶颈不在一次搜索本身(
关键观察:把所有点对的可达关系一次算完。 询问的可能结果总共只有
之后每次询问就退化成一次数组定位,
次基本操作,在 1000 ms 的时限下只占很小的余量。
另一种写法? Floyd 传递闭包(或用 bitset 加速)也是
正确性。 BFS 只在存在 reach[s][v] = 1 蕴含 reach[s][v] = 1(充分性)。
两者合起来即"矩阵的第
代码
Python 版:
#!/usr/bin/env python3
# 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-10-08 07:33
# update_at: 2026-10-08 07:33
import sys
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[list[int]] # 邻接表:adj[u] 是 u 的全部出边终点
def reachable_from(adj: Adj, s: int) -> bytearray:
"""从起点 s 出发搜索全图,返回标记可达点的紧凑数组(下标即点编号,1 表示可达)。
有向图上单源可达性,BFS/DFS 等价;这里用列表当栈,避免递归改写成迭代。
起点自身先标记(路径长度可为 0),入栈时即标记,保证每个点最多进栈一次。
"""
seen = bytearray(len(adj)) # 下标 0 空着不用,点编号从 1 开始
seen[s] = 1
stack = [s]
while stack:
u = stack.pop()
for v in adj[u]:
if not seen[v]: # 入栈同时标记,避免同一个点被重复压栈
seen[v] = 1
stack.append(v)
return seen
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m, k = next(data), next(data), next(data)
adj: Adj = [[] for _ in range(n + 1)]
for _ in range(m):
u = next(data)
v = next(data)
adj[u].append(v) # 有向边,只记 u -> v 这一个方向
# 每个起点各搜一次,得到全源可达性;下标 0 位空着,与非规格输入无歧义
reach = [reachable_from(adj, s) for s in range(n + 1)]
out: list[str] = []
for _ in range(k):
x = next(data)
y = next(data)
out.append("Yes" if reach[x][y] else "No")
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-10-08 07:33
* update_at: 2026-10-08 07:33
*/
// main.cpp:有向图的可达性查询,对每个起点各跑一次 BFS 预处理出全源可达矩阵,
// 之后每次询问 O(1) 查表。与 main.py 同一算法。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1005; // 点数上限 10^3(题面 1 <= N, M <= 10^3),留一点余量
const int MAXM = 1005; // 边数上限同上
int n, m, k; // 点数、边数、询问数
struct Edge { // 链式前向星的一条出边:指向 to,同起点的下一条边编号是 nxt
int to;
int nxt;
};
Edge edge[MAXM];
int head[MAXN]; // head[u] = u 的第一条出边编号,0 表示没有出边
int ecnt; // 已存边数
char reach[MAXN][MAXN]; // reach[s][v]:从 s 出发能否抵达 v;只有 0/1,用 char 省内存
int que[MAXN]; // 手写 BFS 队列,每个点在每个起点下最多入队一次,容量 N 足够
// 加入一条有向边 u -> v(只存 u 到 v 这一个方向)
void add_edge(int u, int v) {
++ecnt;
edge[ecnt].to = v;
edge[ecnt].nxt = head[u];
head[u] = ecnt;
}
// 从起点 s 出发 BFS,把 s 能抵达的点全部标记进 reach[s][*]
void bfs_from(int s) {
int qh = 0, qt = 0;
reach[s][s] = 1; // 路径长度可以为 0,任何点都能抵达自己
que[qt++] = s; // 入队即标记,避免同一个点被重复入队
while (qh < qt) {
int u = que[qh++];
for (int e = head[u]; e; e = edge[e].nxt) {
int v = edge[e].to;
if (!reach[s][v]) {
reach[s][v] = 1;
que[qt++] = v;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v); // 有向图,不要加成双向边
}
// 每个起点单独跑一次 BFS:不能因为 reach[s][s] 被别的起点标过就跳过起点 s
for (int s = 1; s <= n; s++) {
bfs_from(s);
}
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
cout << (reach[x][y] ? "Yes" : "No") << "\n";
}
return 0;
}复杂度
- 时间:预处理对
个起点各跑一次 BFS,每次 ,共 ; 询问阶段 次 查表。总计 。 时预处理约 次操作,实测毫秒级(限时 1000 ms)。 - 空间:可达矩阵
, 时用 char存是 1 MB(C++ 里实测峰值内存远低于 64 MB 限制); 邻接表,BFS 队列 。总计 。 - 与
的关系:整个算法的代价与询问次数无关,这正是本题唯一值得强调的一点—— 题面没给 的上界,而解法的正确性和效率都不依赖它。 - Python 侧:同一算法用列表当栈做迭代式搜索,可达标记存在
bytearray里 (字节,比 bool的嵌套列表省),C++ 与 Python 同为, 不存在因为语言而被迫降级成暴力枚举的情况。
总结
- 静态结构先做一次性预处理:图不随询问变化,就把"所有点对的可达关系"一次算清,
把
次查询从"各搜一遍"压成"各查一次"。这是"在线重复查询 + 离线预处理"的经典换法。 - 规模小也是一种信号:
意味着 的布尔矩阵只有 个格子, 完全存得下——能不能预处理,先看 或 的量级撑不撑得住。 - 两种闭包写法的取舍:多源 BFS 是
,Floyd 是 ; 稀疏图上前者更快,且"从一个点出发能走到哪"就是 BFS 的本义。 - 两个容易写错的细节:一是必须对每个起点都独立重跑搜索——不能因为
reach[s][s]已被别的起点标过就跳过起点,那样只会得到别人可达集的子集; 二是 的询问按"路径长度可为 "判 Yes,这也符合本题数据的口径。
图示解析
以题面样例(
flowchart LR
N1["1"] --> N2["2"] --> N4["4"] --> N3["3"]
两次询问的差别恰好体现了「有向」二字:
| 询问 | 是否存在有向路径 | 输出 | 依据 |
|---|---|---|---|
| 是, |
Yes |
reach[1][3] 在 BFS 中被标为 1 |
|
| 否,链上只能单向向后走 | No |
reach[4][*] 只含 4 和 3 |
对比第 4 行还能看出「可达矩阵逐行独立」的含义:reach[1] 是 reach[4] 只有