查找文献

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

有向图从 1 号点出发,邻接表按编号升序排序后分别做先序 DFS 与 BFS,输出两行可达文章序列。

OJ: roj

题目 ID: 2125

难度:普及-

标签:图论深度优先搜索广度优先搜索python

创建: 2026-10-08 07:39

更新: 2026-10-08 07:39

形式化题目

有 nn 篇文章(编号 1∼n1 \sim n)与 mm 条引用关系,第 ii 条为有向边 Xi→YiX_i \to Y_i, 含义是"文章 XiX_i 的参考文献中有文章 YiY_i"。

文章 XX 看过之后,它引用的文章都要看(已经看过的跳过)。从 11 号文章开始阅读, 出一张阅读顺序表:每个能看到的文章恰好出现一次,当同一时刻有若干篇可看的文章时, 先看编号较小的那篇。

求两行输出:

  • 第一行:按上述规则深度优先得到的阅读序列(DFS 先序);
  • 第二行:按上述规则广度优先得到的阅读序列(BFS)。

注意两点:图是有向的、且可能有自环与重边;从 11 号文章出发不可达的文章 不输出(11 号文章本身一定输出)。规模为 n⩽105n \leqslant 10^5、m⩽106m \leqslant 10^6。

以样例为例,边集为

1→2, 1→3, 1→4, 2→5, 2→6, 3→7, 4→7, 4→8, 7→8,1 \to 2,\ 1 \to 3,\ 1 \to 4,\ 2 \to 5,\ 2 \to 6,\ 3 \to 7,\ 4 \to 7,\ 4 \to 8,\ 7 \to 8,

从 11 出发,DFS 会先一头扎到 22,再扎到 22 的最小出边 55、66,回来后轮到 3→7→83 \to 7 \to 8, 最后才回头访问 44(因 44 早已被 11 引用过,但深搜把它排在最后), 得到 1 2 5 6 3 7 8 4;BFS 逐层展开则是 1 2 3 4 5 6 7 8。

正解

思路

把引用关系看成有向图的边,问题就是一次有向图遍历。难点全在"同一时刻可看的文章, 先看编号较小的那篇"这句话——它要求每个点的出边在遍历时按终点编号升序展开。

于是先建邻接表,再对每个点 u 把 g[u] 原地升序排序。排序只做一次,之后遍历时 顺着 g[u] 逐个走即可,"比较编号"这个动作就被消灭了:出边的物理顺序就是访问顺序。 这一点是本题的全部关键,剩下的 DFS / BFS 都是模板。

为什么不能省掉排序、或者改用别的方式挑最小邻居?因为要求是静态的: 图在读完输入后不再变化,编号的大小关系在任何时候都固定。一次性排序把 “每步挑最小"从"遍历时决策"变成"读表”,代价只付一次。

DFS 有两种正确写法,但坑不一样:

写法 形态 风险
递归 dfs(u) 里对每个未访问邻居递归 n=105n = 10^5 的链状图会爆系统栈;Python 必须改迭代
显式栈模拟递归 栈里存 (结点, 下一个待扩展的出边下标) 无栈溢出风险,且能严格对应递归先序

真正需要小心的是"小技巧版"显式栈:把邻居倒序压栈、出栈时才判重。这种做法虽然 多数情况下答案正确,但它的访问时刻和递归先序并不严格一致(判重发生在出栈时而非入栈时), 分析正确性的成本远高于收益。本解采用携带出边下标的显式栈:入栈时即输出、即标记, 弹出条件与递归的"出边走完"完全对应,正确性可以逐行对照递归版证明。

BFS 则没有争议:入队时标记并输出(出队时输出也一样,但入队时判重能保证每个点只入队 一次,队列长度上限恰好是 nn)。

还有一个容易踩的坑:两趟遍历必须各用一套访问标记。DFS 跑完后所有可达点都已被标记, 若 BFS 复用同一个数组,BFS 会在起点处立刻结束,第二行只剩一个 1。

另外,只输出从 11 可达的点,所以不需要(也不应该)对 1∼n1 \sim n 其余点补跑搜索。

代码

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

import sys
from collections import deque
from collections.abc import Iterator

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Graph = list[list[int]]  # g[u] = u 引用的文章编号,已按编号升序排好


def read_graph(n: int, m: int, data: Iterator[int]) -> Graph:
    """读入 m 条有向边,返回出边升序排序后的邻接表(下标 1..n 对应文章编号)。"""
    g: Graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        x, y = next(data), next(data)
        g[x].append(y)
    for edges in g:
        edges.sort()  # 题面要求:能看的文章多时先看编号小的
    return g


def dfs_order(g: Graph) -> list[int]:
    """从 1 号文章出发的先序 DFS 序列;显式栈代替递归,避免长链爆栈。"""
    order = [1]
    seen = [False] * len(g)
    seen[1] = True
    stack = [(1, 0)]  # (结点, 下一个待扩展的出边下标),栈顶就是当前递归层
    while stack:
        u, idx = stack[-1]
        if idx < len(g[u]):
            stack[-1] = (u, idx + 1)
            v = g[u][idx]
            if not seen[v]:  # 未看过才深入,看过就换下一条出边
                seen[v] = True
                order.append(v)
                stack.append((v, 0))
        else:
            stack.pop()  # 出边走完,回溯
    return order


def bfs_order(g: Graph) -> list[int]:
    """从 1 号文章出发的 BFS 序列;出队时按升序展开出边,入队即判重。"""
    order = [1]
    seen = [False] * len(g)
    seen[1] = True
    q = deque([1])
    while q:
        u = q.popleft()  # 队首文章,按升序展开它的参考文献
        for v in g[u]:
            if not seen[v]:
                seen[v] = True
                order.append(v)
                q.append(v)
    return order


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)  # 文章数、引用关系数
    g = read_graph(n, m, data)
    # 两行答案:先 DFS 序列,再 BFS 序列
    out = (" ".join(map(str, dfs_order(g))), " ".join(map(str, bfs_order(g))))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版本同一算法,DFS 同样是携带出边下标的显式栈:

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:39
 * update_at: 2026-10-08 07:39
 */
// main.cpp:查找文献。有向图 X->Y 表示文章 X 引用了文章 Y,
// 从 1 号文章出发,出边按编号升序排序后分别做 DFS / BFS,只输出可达文章。
// DFS 用显式栈模拟递归先序,链状图深度 1e5 也不会爆系统栈。

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

typedef long long ll;

const int MAXN = 100005; // 文章编号上限 1e5,开 1e5+5 够用

int n, m;              // 文章数、引用关系数(值域 <= 1e6,int 足够)
vector<int> g[MAXN];   // 邻接表:g[u] 存 u 的参考文献(读数后统一升序排序)
int ans[MAXN];         // 遍历序列(最多 n 个数)
bool vis[MAXN];        // 访问标记;DFS 与 BFS 各自重算一次,必须清零复用

// 显式栈的一帧:结点 u,以及"下一个待扩展的出边下标"
struct Frame {
    int u;
    int idx;
};
Frame stk[MAXN]; // 栈深最多 n(链状图)

// 打印一个序列,数字间单空格,行末不加多余空格
void print_seq(int cnt) {
    for (int i = 0; i < cnt; i++) {
        printf("%d%c", ans[i], i + 1 == cnt ? '\n' : ' ');
    }
}

// 从 1 号文章出发的先序 DFS:显式栈严格对应递归写法(访问即输出,回溯靠弹栈)
int dfs() {
    for (int i = 1; i <= n; i++) vis[i] = false;
    int cnt = 0;
    int top = 0;
    vis[1] = true;
    ans[cnt++] = 1;
    stk[top].u = 1;
    stk[top].idx = 0;
    top++;
    while (top > 0) {
        int u = stk[top - 1].u;
        if (stk[top - 1].idx < (int)g[u].size()) {
            int v = g[u][stk[top - 1].idx];
            stk[top - 1].idx++;
            if (!vis[v]) { // 未看过才递归进去,看过就换下一条出边
                vis[v] = true;
                ans[cnt++] = v;
                stk[top].u = v;
                stk[top].idx = 0;
                top++;
            }
        } else {
            top--; // 出边走完,回溯
        }
    }
    return cnt;
}

// 从 1 号文章出发的 BFS:入队时判重,保证每个点只入队一次
int bfs() {
    for (int i = 1; i <= n; i++) vis[i] = false;
    int cnt = 0;
    queue<int> q;
    vis[1] = true;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans[cnt++] = u;
        int sz = g[u].size();
        for (int i = 0; i < sz; i++) {
            int v = g[u][i];
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    return cnt;
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
    }
    // 题面:能看的文章很多时先看编号较小的那篇 -> 出边升序排序
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
    }

    print_seq(dfs());
    print_seq(bfs());

    return 0;
}

复杂度

设 ∑d(u)=m\sum d(u) = m。

  • 建图 O(n+m)O(n + m);对每个点排序出边,总计 O ⁣(∑ud(u)log⁡d(u))⩽O(mlog⁡n)O\!\left(\sum_{u} d(u) \log d(u)\right) \leqslant O(m \log n);
  • DFS 与 BFS 各 O(n+m)O(n + m)——每个可达点进出一次,每条出边恰好被扫一次;
  • 总时间 O(n+mlog⁡n)O(n + m \log n),空间 O(n+m)O(n + m)。

n=105n = 10^5、m=106m = 10^6 时,瓶颈是排序的约 2×1072 \times 10^7 次比较与 10610^6 条边的读写, 远低于 1000 ms / 128 MB。Python 版在顶格数据下受解释器常数影响,可能超出 1 s (属允许范围),但算法与 C++ 版同阶,没有降级为暴力。

总结

  • 本题是"有序邻居遍历"的模板题:把局部贪心变成一次全局排序,是处理 "每次取最小 / 最大邻居"这类要求的通用套路,比用堆做在线决策更省常数、更好证明。
  • 递归 DFS 在 n=105n = 10^5 的链上会爆栈,显式栈是标配;而"倒序压栈出栈判重"虽然短, 与递归先序的对应关系不直观,教学上不如携带出边下标的写法。
  • 同一张图跑两遍遍历时,访问标记必须重置——这类"共享状态忘了清"是本题最常见的失分点。
  • 只输出可达点意味着不用补搜其余连通块,起点固定为 11 也免去了多源处理的讨论。

说明

本题素材源(new_ROJ/problems/2125/)自带 data.py 数据生成脚本,10 个测试点是 用 cyaron 按题面范围自行生成的(点 1~2 为边界、3~6 为随机中小规模、7 为含不可达点的 大规模、8~10 为顶格 n=105,m=106n = 10^5, m = 10^6 的随机 / 链 / 菊花结构),题面文字亦为网络重建版本。 因此出题意图可能与官方原题(同题意为洛谷 P5318)存在偏差;本解法以题面文字为准, 并已在全部 10 个测试点上验证通过。

图示解析

这张图对比同一张样例图上的两种遍历:DFS 是"一条路走到底再回头", BFS 是"逐层推进",两条序列的差别全部来自搜索方式,与排序无关。

flowchart TD
  R["1"] --> A["2"]
  R --> B["3"]
  R --> C["4"]
  A --> D["5"]
  A --> E["6"]
  B --> F["7"]
  C --> F
  C --> G["8"]
  F --> G
  • DFS 序列 1 2 5 6 3 7 8 4:从 11 顺着最小出边 22 深入,22 的最小出边 55 是叶子, 回溯后走 66,再回到 22、回到 11,接着走 3→7→83 \to 7 \to 8(88 已在 77 处访问过), 最后才处理 11 的第三条出边 44。
  • BFS 序列 1 2 3 4 5 6 7 8:11 出队后把 2,3,42, 3, 4 依次入队,之后每层各自展开—— 恰好就是编号升序,因为每层的出边都排过序,而"层"的顺序由队列先进先出固定。

注意 88 在两条序列中都只在第一次到达时出现:4→84 \to 8 与 7→87 \to 8 是两条不同的边, 但终点是同一篇文章,判重只认文章编号。