图的存储与访问

GitHub跳转原题关系图返回列表

有向图上对每个起点各跑一次 BFS 预处理全源可达矩阵,此后每次询问 O(1) 查表回答 Yes/No。

OJ: roj

题目 ID: 2123

难度:普及-

标签:图论BFS传递闭包python

创建: 2026-10-08 07:33

更新: 2026-10-08 07:33

形式化题目

给定一个有向图 G=(V,E)G = (V, E),∣V∣=N|V| = N、∣E∣=M|E| = M,顶点编号 1,2,…,N1, 2, \dots, N。 随后有 KK 次询问,每次给出有序对 (X,Y)(X, Y),判断是否存在有向路径

X⇝Y,X \rightsquigarrow Y,

即从 XX 出发沿边的方向走若干条边(长度可以为 00,因此 X=YX = Y 恒为可达)能否到达 YY。 能到达输出 Yes,否则输出 No,共 KK 行。

约束:1⩽N,M⩽1031 \leqslant N, M \leqslant 10^3。题面没有声明 KK 的上限, 这直接决定了算法选择(见下文)。

数据说明:本题题面与测试数据均由仓库内的生成脚本自造(素材源带 data.py), 并非官方原始数据;题面本身的来源是「信息学奥赛一本通 · 数据结构基础 · 第四章 图论算法」。 生成脚本取 1⩽K⩽1031 \leqslant K \leqslant 10^3(与 NN、MM 同量级,属于工作范围而非题面声明), 并刻意包含自环、重边、长链与强连通环;对 X=YX = Y 的询问只在与「路径长度 ⩾1\geqslant 1」 的读法结论一致时才出现,因此数据不依赖「长度 00 算不算可达」这处语义选择。

正解

思路

朴素做法。 每次询问现场搜索一遍:从 XX 出发 BFS/DFS,碰到 YY 就输出 Yes, 搜完整张图都没碰到就输出 No。单次代价 O(N+M)O(N + M),总代价 O(K(N+M))O(K(N + M))。

瓶颈在哪? 瓶颈不在一次搜索本身(N+M⩽2000N + M \leqslant 2000 很小), 而在于重复:如果连着问同一批起点,同一张子图会被反复搜上很多遍。 KK 没有上界,K(N+M)K(N + M) 就跟着没有上界。真正浪费的是"图的边集在所有询问中恒定不变" 这个事实——既然图是静态的,就没有任何理由为每次询问重算一遍。

关键观察:把所有点对的可达关系一次算完。 询问的可能结果总共只有 N2N^2 种点对, 而 N⩽103N \leqslant 10^3,于是 N2⩽106N^2 \leqslant 10^6。只要预处理出布尔矩阵

reach[s][v]={1,s⇝v,0,否则,\mathrm{reach}[s][v] = \begin{cases} 1, & s \rightsquigarrow v,\\ 0, & \text{否则}, \end{cases}

之后每次询问就退化成一次数组定位,O(1)O(1),与 KK 完全无关。 预处理的办法是最直白的一种:以每个点为起点各跑一次 BFS, 每次 O(N+M)O(N + M),总共

O(N(N+M))=1000×(1000+1000)=2×106O\bigl(N(N + M)\bigr) = 1000 \times (1000 + 1000) = 2 \times 10^6

次基本操作,在 1000 ms 的时限下只占很小的余量。

另一种写法? Floyd 传递闭包(或用 bitset 加速)也是 O(N3/64)O(N^3 / 64), 同样能过,编码也不算难。但在 M⩽103M \leqslant 10^3 的稀疏图上, 多源 BFS 的 O(N(N+M))O(N(N+M)) 严格更优(这里是 2×1062 \times 10^6 而 Floyd 是 109/64≈1.5×10710^9 / 64 \approx 1.5 \times 10^7), 而且"从一个点出发能走到哪"正是 BFS 的字面语义,不需要引入新的状态维度。 本题选多源 BFS。

正确性。 BFS 只在存在 s→vs \to v 的有向边时才把 vv 标记为可达, 每次标记都对应一条真实的路径前缀,所以 reach[s][v] = 1 蕴含 s⇝vs \rightsquigarrow v(必要性); 反过来,若存在路径 s=w0→w1→⋯→wℓ=vs = w_0 \to w_1 \to \cdots \to w_\ell = v,对 ℓ\ell 归纳可知 BFS 会依次标出 w1,…,wℓw_1, \dots, w_\ell,故 reach[s][v] = 1(充分性)。 两者合起来即"矩阵的第 ss 行恰是 ss 的可达集"。预处理后逐条查表,答案自然正确。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:预处理对 NN 个起点各跑一次 BFS,每次 O(N+M)O(N + M),共 O(N(N+M))O\bigl(N(N + M)\bigr); 询问阶段 KK 次 O(1)O(1) 查表。总计 O(N(N+M)+K)O\bigl(N(N + M) + K\bigr)。 N=M=103N = M = 10^3 时预处理约 2×1062 \times 10^6 次操作,实测毫秒级(限时 1000 ms)。
  • 空间:可达矩阵 O(N2)O(N^2),N=103N = 10^3 时用 char 存是 1 MB(C++ 里实测峰值内存远低于 64 MB 限制); 邻接表 O(N+M)O(N + M),BFS 队列 O(N)O(N)。总计 O(N2+M)O(N^2 + M)。
  • 与 KK 的关系:整个算法的代价与询问次数无关,这正是本题唯一值得强调的一点—— 题面没给 KK 的上界,而解法的正确性和效率都不依赖它。
  • Python 侧:同一算法用列表当栈做迭代式搜索,可达标记存在 bytearray 里 (N2=106N^2 = 10^6 字节,比 bool 的嵌套列表省),C++ 与 Python 同为 O(N(N+M)+K)O(N(N+M) + K), 不存在因为语言而被迫降级成暴力枚举的情况。

总结

  • 静态结构先做一次性预处理:图不随询问变化,就把"所有点对的可达关系"一次算清, 把 KK 次查询从"各搜一遍"压成"各查一次"。这是"在线重复查询 + 离线预处理"的经典换法。
  • 规模小也是一种信号:N⩽103N \leqslant 10^3 意味着 N2N^2 的布尔矩阵只有 10610^6 个格子, 完全存得下——能不能预处理,先看 N2N^2 或 N3N^3 的量级撑不撑得住。
  • 两种闭包写法的取舍:多源 BFS 是 O(N(N+M))O(N(N+M)),Floyd 是 O(N3/bitset)O(N^3/\text{bitset}); 稀疏图上前者更快,且"从一个点出发能走到哪"就是 BFS 的本义。
  • 两个容易写错的细节:一是必须对每个起点都独立重跑搜索——不能因为 reach[s][s] 已被别的起点标过就跳过起点 ss,那样只会得到别人可达集的子集; 二是 X=YX = Y 的询问按"路径长度可为 00"判 Yes,这也符合本题数据的口径。

图示解析

以题面样例(N=4N = 4,边 1→21 \to 2、2→42 \to 4、4→34 \to 3)为例。 这张图是一条 1→2→4→31 \to 2 \to 4 \to 3 的长链,预处理时从 1 出发的一次 BFS 就能把 2,4,32, 4, 3 全部标成可达:

flowchart LR
    N1["1"] --> N2["2"] --> N4["4"] --> N3["3"]

两次询问的差别恰好体现了「有向」二字:

询问 是否存在有向路径 输出 依据
(1,3)(1, 3) 是,1→2→4→31 \to 2 \to 4 \to 3 Yes reach[1][3] 在 BFS 中被标为 1
(4,1)(4, 1) 否,链上只能单向向后走 No reach[4][*] 只含 4 和 3

对比第 4 行还能看出「可达矩阵逐行独立」的含义:reach[1] 是 {1,2,3,4}\{1,2,3,4\}, 而 reach[4] 只有 {3,4}\{3,4\}——从 4 出发连 2 都到不了,更不用说到 1。 这正是为什么预处理必须对每个起点各跑一次,而不能靠某一行去推另一行。