【深基18.例3】查找文献

题意

给出一个有向图，从 1 号点出发，分别输出：

按题目要求进行的 DFS 遍历顺序
按题目要求进行的 BFS 遍历顺序

如果某一步有多个可选点，必须先访问编号较小的那个。

思路

最直接的做法就是照定义写 DFS 和 BFS。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#include <bits/stdc++.h>
using namespace std;

static vector<vector<int>> g;
static vector<int> vis;
static vector<int> dfs_order;
static vector<int> bfs_order;

void dfs(int u) {
    vis[u] = 1;
    dfs_order.push_back(u);
    for (int v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
    }

    vis.assign(n + 1, 0);
    dfs(1);
    for (int x : dfs_order) {
        cout << x << ' ';
    }
    cout << '\n';

    fill(vis.begin(), vis.end(), 0);
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        bfs_order.push_back(u);
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                q.push(v);
            }
        }
    }

    for (int x : bfs_order) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

brute.cpp 用递归 DFS 和普通队列 BFS 实现了最直观的版本，适合小图对拍。

真正需要注意的是访问顺序和栈深：

邻接表必须先按升序排序
BFS 直接按升序扩展邻居即可
正式解里的 DFS 不建议用递归，因为 n 可达 1e5

这张图展示样例结构：

digraph G {
  1 -> 2;
  1 -> 3;
  1 -> 4;
  2 -> 5;
  2 -> 6;
  3 -> 7;
  4 -> 7;
  4 -> 8;
  7 -> 8;
}

从图里可以看出，BFS 很自然是一层一层访问；而 DFS 则需要优先深入编号更小的后继。所以正式解采用“邻接表升序 + 逆序压栈”的方式，用显式栈模拟递归 DFS 的顺序。

Python 知识

deque 的 popleft() 是 $O(1)$ ，适合作为 BFS 队列。
非递归 DFS 用列表作栈；邻接表升序后以 reversed(graph[node]) 逆序压栈，弹出时才会优先访问小编号。
bytearray(n+1) 比 Python 布尔列表更紧凑，适合十万点访问标记。
逐行读入百万条边，避免 read().split() 同时保留两百万个临时 token。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：deque 队列和容器选择。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：递归深度与输入内存。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43import sys
from collections import deque


def main():
    read = sys.stdin.buffer.readline
    n, m = map(int, read().split())
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, read().split())
        graph[u].append(v)
    for neighbors in graph:
        neighbors.sort()

    visited = bytearray(n + 1)
    dfs_order = []
    stack = [1]
    while stack:
        node = stack.pop()
        if visited[node]:
            continue
        visited[node] = 1
        dfs_order.append(node)
        stack.extend(reversed(graph[node]))

    visited = bytearray(n + 1)
    visited[1] = 1
    bfs_order = []
    queue = deque([1])
    while queue:
        node = queue.popleft()
        bfs_order.append(node)
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = 1
                queue.append(neighbor)

    print(*dfs_order)
    print(*bfs_order)


if __name__ == "__main__":
    main()

stl 代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104/**
 * 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-09 19:13
 * update_at: 2026-10-09 19:13
 */
// main.cpp：P5318 查找文献。
// 代码分层：读入 / 建图排序 / DFS / BFS 各一个函数，main 只按顺序调用；
// 图、访问标记这些核心数据放全局，函数之间共享，比一大段 main 清楚。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, m; // 文章数（点）和引用关系数（边）

// g[u]：文章 u 引用的所有文章编号，按编号升序（编号 ≤ 1e5，用 int 存）
vector<vector<int>> g;
vector<int> visited; // visited[u]：0 表示这篇文章还没看过，1 表示已经看过

// 读入 n、m 和 m 条引用关系，建出邻接表
void read_input() {
    cin >> n >> m;

    g.assign(n + 1, vector<int>());
    for (ll i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
}

// 每个点的引用列表按编号升序排好，之后才能保证“先看编号小的文章”
void build_graph() {
    for (ll u = 1; u <= n; u++) {
        sort(g[u].begin(), g[u].end());
    }
}

// 非递归 DFS：手工栈模拟递归，避免 n = 1e5 时递归爆栈
void dfs_solve() {
    visited.assign(n + 1, 0);

    stack<int> st;
    st.push(1); // 起点是 1 号文章

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (visited[u] == 1) {
            continue; // 这个点更早的时候已经被访问过了
        }
        visited[u] = 1;
        cout << u << ' ';

        // 引用列表是升序的，从最后一条往前压栈，编号小的邻居后进栈、先弹出
        ll deg = g[u].size();
        for (ll i = deg - 1; i >= 0; i--) {
            int v = g[u][i];
            if (visited[v] == 0) {
                st.push(v);
            }
        }
    }
    cout << '\n';
}

// BFS：普通队列按层扩展，每层按编号升序入队
void bfs_solve() {
    visited.assign(n + 1, 0);

    queue<int> q;
    q.push(1);
    visited[1] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << ' ';

        ll deg = g[u].size();
        for (ll i = 0; i < deg; i++) {
            int v = g[u][i];
            if (visited[v] == 0) {
                visited[v] = 1;
                q.push(v);
            }
        }
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    build_graph();
    dfs_solve();
    bfs_solve();

    return 0;
}

链式前向星版本

上面用 list 当邻接表。换成 C++ 手写时也可以不用 vector<vector<int>>，改用链式前向星：把 $m$ 条边读进 pair 数组，按 $(u,v)$ 升序排序，再从后往前插入前向星。这样点 $u$ 最后插入的是它编号最小的邻居，边表头指向它，遍历出边时天然就是升序——把“逐点排序”换成了“对整张边表排序一次”。DFS 和 BFS 共用同一个 for_each 遍历出边。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93/* author: Rainboy email: rainboylvx@qq.com  time: 2022年 01月 16日 星期日 14:48:43 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5,maxe = 1e6+5; //点与边的数量

int n,m;
/* 定义全局变量 */

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){	//构造函数
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }
    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }
    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    edge& operator[](int i){
        return e[i];
    }
} e;

vector<pair<int,int>> v1;

bool vis[maxn];
void dfs(int u){
    vis[u] = 1;
    printf("%d ",u);
    int i;
    e.for_each(u, [&](int u,int v,int w){
        if(vis[v] == 0){
            vis[v] = 1;
            dfs(v);
        }
    });
}

void bfs(int u){
    queue<int> q;
    vis[u] = 1;
    q.push(u);
    while ( !q.empty() ) {
        int u = q.front();
        q.pop();
        printf("%d ",u);
        int i;
        e.for_each(u, [&](int u,int v,int w){
            if(vis[v] == 0){
                vis[v] = 1;
                q.push(v);
            }
        });
    }
}

int main(int argc,char * argv[]){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        //v1.emplace_back(u,v);
        v1.push_back(std::make_pair(u,v));
    }
    sort(v1.begin(),v1.end());
    //std::reverse(v1.begin(), v1.end());
    //for (const auto& ee : v1) {
        //e.add(ee.first,ee.second);
    //}
    for(int i = v1.size()-1; i>=0;i--){
        e.add(v1[i].first, v1[i].second);
    }
    dfs(1);
    printf("\n");
    memset(vis,0,sizeof(vis));
    bfs(1);
    return 0;

}

这份实现的思路和正式解一致，唯一要留意的是 DFS 写成了递归：链状数据下递归深度可达 $10^5$ ，有爆栈风险，所以正式解改用显式栈模拟。

复杂度

建图后需要对各邻接表排序，然后各做一次 DFS 和 BFS。时间复杂度上界为 $O(m\log m+n+m)$ ，空间复杂度 $O(n+m)$ 。

总结

这题本身不难，关键在两个实现细节：邻接表要排序，非递归 DFS 要逆序压栈。把这两个点处理好，答案就稳定了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。