图的遍历

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

反向建图后从 N 到 1 倒序 BFS 染色,每个点首次被覆盖时的起点编号就是它能到达的最大编号点,总体 O(N+M)。

OJ: roj

题目 ID: 2124

难度:普及+/提高-

标签:图论反向建图BFSpython

创建: 2026-10-08 07:36

更新: 2026-10-08 07:36

形式化题目

给定有向图 G=(V,E)G = (V, E),V={1,2,…,N}V = \{1, 2, \dots, N\},∣E∣=M|E| = M(允许自环与重边)。

对每个点 vv,记它的可达集为

R(v)={ u∈V∣v⇝u },v∈R(v),R(v) = \{\, u \in V \mid v \rightsquigarrow u \,\}, \qquad v \in R(v),

也就是从 vv 出发顺着有向边能走到的全部点(含 vv 自身)。 要求输出每个点上的函数值

A(v)=max⁡u∈R(v)u.A(v) = \max_{u \in R(v)} u .

即"从 vv 出发,能到达的编号最大的点"。输出一行 NN 个数 A(1),A(2),…,A(N)A(1), A(2), \dots, A(N),以空格分隔。数据范围 1⩽N,M⩽1051 \leqslant N, M \leqslant 10^5, 限时 1000 ms,内存 128 MB。

正解

思路

朴素做法。 对每个 vv 从它自己出发做一次 BFS/DFS,把能走到的点全标出来, 最后在标记里取最大编号。单次搜索 O(N+M)O(N+M),总共 O(N(N+M))O\big(N(N+M)\big): N=M=105N = M = 10^5 时约 101010^{10} 次操作,远超 1000 ms 能承受的量级,必然超时。 瓶颈是同一张图被从头遍历了 NN 遍,而 NN 遍里绝大多数工作是完全重复的。

换方向:把"谁被谁到达"反过来问。 这里的关键是"最大编号"这个目标, 它自带一个单调顺序可以利用。把每条边反向,得到反图 G′=(V,E′)G' = (V, E'), E′={ (v,u)∣(u,v)∈E }E' = \{\, (v, u) \mid (u, v) \in E \,\}。在原图中"vv 能到达 uu" 等价于在反图中"uu 能到达 vv",于是原来的 A(v)A(v) 可以换个说法:

A(v)A(v) 等于反图中能到达 vv 的、编号最大的那个起点。

贪心地倒序染色。 既然要最大编号,就让编号大的起点先动手: 依次枚举起点 u=N,N−1,…,1u = N, N-1, \dots, 1。如果 uu 还没被染过色,就在反图上从 uu 做一次 BFS,把沿途所有尚未染色的点 vv 全部染上颜色 uu(即令 A(v)=uA(v) = u)。 正确性来自两点:

  1. 染色时的 uu 确实能到 vv(反图上的路径反过来就是原图 v→uv \to u 的路径),所以 u∈R(v)u \in R(v);
  2. 所有比 uu 大的起点都已经被处理过了。若其中某一个大编号 u′u' 也能到达 vv, 那 vv 在 u′u' 那一轮就该被染上色,不会被留到这一轮——所以现在染的 uu 就是能到达 vv 的最大编号。

剪枝发生在"已染色就跳过"这一句。 已染色的起点不再发起搜索, 已染色的点也不再入队,于是反图的每个点和每条边在整个过程中最多被检查一次, 总复杂度降到 O(N+M)O(N+M),与 NN 次搜索的 O(N(N+M))O\big(N(N+M)\big) 相比是数量级的差距。

以题面样例为例,N=4N=4、边为 1→21 \to 2、2→42 \to 4、4→34 \to 3, 反图为 2→12 \to 1、4→24 \to 2、3→43 \to 4:

起点 uu 起点是否已染色 反图中从 uu 走到的新点 本轮写入的答案
4 否 2, 1(4→2→14 \to 2 \to 1) A(4)=A(2)=A(1)=4A(4)=A(2)=A(1)=4
3 否 无(3→43 \to 4 的 4 已染色) A(3)=3A(3)=3
2 是 — —
1 是 — —

得到 A=(4,4,3,4)A = (4, 4, 3, 4),与样例输出一致。注意 A(3)=3A(3) = 3:在原图里 33 没有出边,只能到达自己。

自环、重边无需特判:自环在反图上是"自己指向自己"的边,被染色标记拦下; 重边被 ans[v] == 0 的判断拦下。孤立点在倒序枚举到自己那一轮以自身为源, 答案自然是 A(v)=vA(v) = v。

实现要点:用 BFS 而不是递归 DFS。 数据里有退化成 1→2→⋯→1000001 \to 2 \to \dots \to 100000 的正向长链,反图就是长度 10510^5 的链,递归 DFS 的系统栈深度会达到 5×1045 \times 10^4 以上,有爆栈风险。基于 queue / deque 的 BFS 逻辑完全等价,且不依赖栈深度。

代码

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:36
# update_at: 2026-10-08 07:36

import sys
from collections import deque

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type ReverseAdj = list[list[int]]  # 反图邻接表:rev[v] 里是所有原图中指向 v 的点


def max_reachable(n: int, rev: ReverseAdj) -> list[int]:
    """返回 ans[1..n]:ans[v] 是从 v 出发在原图中能到达的最大编号点。

    反图里 u -> v 的边表示"原图中 v 能走到 u",所以从 u 出发的搜索覆盖到的点 v
    都在原图中能到达 u。按起点编号从大到小串行染色,编号大的起点先动手,
    某点第一次被染色就取该起点的编号。
    """
    ans = [0] * (n + 1)
    for start in range(n, 0, -1):
        if ans[start]:
            continue                 # 已被更大编号的起点覆盖,答案不会再变小
        ans[start] = start           # 每个点至少能到达自己
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in rev[u]:
                if not ans[v]:       # 只在首次到达时染色,每个点至多入队一次
                    ans[v] = start
                    queue.append(v)
    return ans


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return
    data = iter(map(int, tokens))

    n, m = next(data), next(data)
    rev: ReverseAdj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = next(data), next(data)
        rev[v].append(u)             # 反向建边:原图 u -> v 换成反图 v -> u

    print(*max_reachable(n, rev)[1:])


if __name__ == "__main__":
    solve()

C++ 版(同一算法,链式前向星存反图 + 手写队列 BFS):

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:36
 * update_at: 2026-10-08 07:36
 */
#include <cstdio>
#include <queue>

typedef long long ll;

const int MAXN = 100005;
const int MAXM = 100005;

int head[MAXN]; // head[u] 是反图中从 u 出发的第一条边的编号,0 表示无出边
int to[MAXM];   // to[i] 是第 i 条边的终点
int nxt[MAXM];  // nxt[i] 是同一起点的下一条边的编号
int edge_cnt;   // 已加入的边数(链式前向星的分配指针)

ll n, m;
ll ans[MAXN]; // ans[v] 表示原图中 v 能到达的最大编号点,0 表示还没被更大的编号覆盖

// 在反图中加入一条 u -> v 的边。
void add_edge(ll u, ll v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 在反图上从 start 出发做 BFS:沿途首次走到的点,在反图中都能走到 start,
// 也就是在原图中能到达 start,于是把它们的答案一次性定为 start。
void bfs(ll start) {
    std::queue<ll> q;
    q.push(start);
    ans[start] = start; // 每个点至少能到达自己

    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll e = head[u]; e != 0; e = nxt[e]) {
            ll v = to[e];
            if (ans[v] == 0) { // 只在这里染色,保证每个点只入队一次
                ans[v] = start;
                q.push(v);
            }
        }
    }
}

int main() {
    if (scanf("%lld %lld", &n, &m) != 2) return 0;

    for (ll i = 1; i <= m; i++) {
        ll u, v;
        scanf("%lld %lld", &u, &v);
        add_edge(v, u); // 反向建边:原图的 u -> v 换成反图的 v -> u
    }

    // 从大到小枚举起点:编号更大的起点先遍历,它第一次到达的点就该取它当答案
    for (ll v = n; v >= 1; v--) {
        if (ans[v] == 0) {
            bfs(v);
        }
    }

    for (ll i = 1; i <= n; i++) {
        printf("%lld%c", ans[i], i == n ? '\n' : ' ');
    }
    return 0;
}

复杂度

  • 时间:外层倒序枚举 NN 次,只有未染色的点才发起搜索;内层每次取出一个点、 扫一遍它的反向出边。每个点至多入队一次,每条反向边至多被检查一次, 总时间 O(N+M)O(N + M)。实测最大测例(N=M=105N = M = 10^5)C++ 约 0.02 s, CPython 约 0.05 s,限时 1000 ms 内余量充足。
  • 空间:反图的链式前向星/邻接表占 O(N+M)O(N+M),答案数组占 O(N)O(N), 总空间 O(N+M)O(N + M)。C++ 实测峰值内存约 8 MB,Python 侧约 20 MB, 均远低于 128 MB。
  • 与朴素解法的对比:朴素解法在提示中 60% 的档位(N,M⩽2000N, M \leqslant 2000) 就已经要 4×1064 \times 10^6 次以上操作、且随规模平方增长,本题的 "反向建图 + 倒序染色"是把可重算的重复遍历彻底省掉的典型手段。

总结

  • 换个方向问问题:把"vv 能到哪些点"改成"哪些点能到 vv",同一个问题就从一个 多源问题变成一个可以一次扫完的问题。反向建图是这类"求每个点的可达极值"的共同起手式。
  • 利用答案的单调序做剪枝:因为要的是最大编号,所以倒序枚举起点, 再用"已染色就跳过"把重复遍历挡在门外。这条剪枝是复杂度从 O(N(N+M))O\big(N(N+M)\big) 降到 O(N+M)O(N+M) 的全部来源——没有它,反图上的 NN 次搜索一样是平方级。
  • 每个点只在首次被覆盖时定案:把"搜索"和"赋值"合成一步, 不需要存下每个点的可达集合,也不需要事后取 max⁡\max。
  • 长链数据优先用 BFS:链状图上递归 DFS 的深度与 NN 同阶,改成显式队列 是本题实现上最实际的注意事项。
  • 本题素材源自带数据生成脚本(data.py,cyaron 分层造数据), 说明 data/ 与题面是网络重建后的产物,与官方原题(本题面同洛谷 P3916, 出自《信息学奥赛一本通》图论部分)的测试数据可能不完全一致; 本解法的正确性只依赖题面描述的模型,10 个数据点全部比对通过。