有向图从 1 号点出发,邻接表按编号升序排序后分别做先序 DFS 与 BFS,输出两行可达文章序列。
OJ: roj
题目 ID: 2125
难度:普及-
标签:图论深度优先搜索广度优先搜索python
创建: 2026-10-08 07:39
更新: 2026-10-08 07:39
形式化题目
有
文章
求两行输出:
- 第一行:按上述规则深度优先得到的阅读序列(DFS 先序);
- 第二行:按上述规则广度优先得到的阅读序列(BFS)。
注意两点:图是有向的、且可能有自环与重边;从
以样例为例,边集为
从 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) 里对每个未访问邻居递归 |
|
| 显式栈模拟递归 | 栈里存 (结点, 下一个待扩展的出边下标) |
无栈溢出风险,且能严格对应递归先序 |
真正需要小心的是"小技巧版"显式栈:把邻居倒序压栈、出栈时才判重。这种做法虽然 多数情况下答案正确,但它的访问时刻和递归先序并不严格一致(判重发生在出栈时而非入栈时), 分析正确性的成本远高于收益。本解采用携带出边下标的显式栈:入栈时即输出、即标记, 弹出条件与递归的"出边走完"完全对应,正确性可以逐行对照递归版证明。
BFS 则没有争议:入队时标记并输出(出队时输出也一样,但入队时判重能保证每个点只入队
一次,队列长度上限恰好是
还有一个容易踩的坑:两趟遍历必须各用一套访问标记。DFS 跑完后所有可达点都已被标记,
若 BFS 复用同一个数组,BFS 会在起点处立刻结束,第二行只剩一个 1。
另外,只输出从
代码
#!/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 同样是携带出边下标的显式栈:
/**
* 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;
}复杂度
设
- 建图
;对每个点排序出边,总计 ; - DFS 与 BFS 各
——每个可达点进出一次,每条出边恰好被扫一次; - 总时间
,空间 。
总结
- 本题是"有序邻居遍历"的模板题:把局部贪心变成一次全局排序,是处理 "每次取最小 / 最大邻居"这类要求的通用套路,比用堆做在线决策更省常数、更好证明。
- 递归 DFS 在
的链上会爆栈,显式栈是标配;而"倒序压栈出栈判重"虽然短, 与递归先序的对应关系不直观,教学上不如携带出边下标的写法。 - 同一张图跑两遍遍历时,访问标记必须重置——这类"共享状态忘了清"是本题最常见的失分点。
- 只输出可达点意味着不用补搜其余连通块,起点固定为
也免去了多源处理的讨论。
说明
本题素材源(new_ROJ/problems/2125/)自带 data.py 数据生成脚本,10 个测试点是
用 cyaron 按题面范围自行生成的(点 1~2 为边界、3~6 为随机中小规模、7 为含不可达点的
大规模、8~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:从顺着最小出边 深入, 的最小出边 是叶子, 回溯后走 ,再回到 、回到 ,接着走 ( 已在 处访问过), 最后才处理 的第三条出边 。 - BFS 序列
1 2 3 4 5 6 7 8:出队后把 依次入队,之后每层各自展开—— 恰好就是编号升序,因为每层的出边都排过序,而"层"的顺序由队列先进先出固定。
注意
请对这个图分别进行 DFS 和 BFS,并输出遍历结果。如果有很多篇文章可以参阅,请先看编号较小的那篇(因此你可能需要先排序)。