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

题目描述

小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$）以及 $m(m\le10^6)$ 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

输入格式

共 $m+1$ 行，第 1 行为 2 个数，$n$ 和 $m$，分别表示一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$）以及$m(m\le10^6)$ 条参考文献引用关系。

接下来 $m$ 行，每行有两个整数 $X,Y$ 表示文章 X 有参考文献 Y。

输出格式

共 2 行。
第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。

输入输出样例 #1

输入 #1

8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8

输出 #1

1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8

【题解】
一道图的遍历的基础入门题。

题目大意可以概括一下：有一张有向图，求其进行深度优先搜索(DFS)和广度优先搜索(BFS)的两个字典序最小的遍历序列。

首先我们得明白什么叫DFS和BFS。

DFS，用通俗的话来说，就是你从图的一个结点出发，选择了下一个你需要遍历的结点，然后你再以你所选择的点作为新的起点，继续向下选择，直到你选择的结点没有了下一个结点，或者它所有的子节点都被访问过。

那么此时怎么办呢？

那你就要按照你选择的路径，依次跳回，直到你跳回的节点有了字节点，再进行遍历，以此类推。

BFS，用通俗的话来说，就是你从图中的一个节点出发，其有几个子节点，你会先将这所有的子节点遍历，再挑其中的一个子节点，遍历它的所有子节点，再换到另外一个结点遍历其所有的子节点。这样一层层遍历，以此类推。

那么该用什么算法实现呢？

对于DFS，由于它需要往回跳，所以就需要用递归算法；

对于BFS，由于它需要一层层遍历，所以需要用一个数据结构来存储每一层的节点，而根据我所描述的，选用队列(queue)是最为合适的。

对了，这道题节点数≤10
5
，使用邻接矩阵会MLE，那么就只能考虑采用邻接表。

又由于本题需要求字典序最小的序列，那么就要将邻接表存储的结点按从小到大进行排序。

总体就是这样的，记得两次遍历中间要清空你遍历时所需要的标记数组。

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100010;

std::vector<int> G[MAXN];
int n, m;
bool visited[MAXN];
queue<int> q;

void dfs(int x, int cur) {//x指当前所在的节点，cur指已遍历过的节点个数
    visited[x] = true;//标记以避免重复访问
    cout << x << " ";//输出
    if (cur == n) return ;
    for (int i=0; i<G[x].size(); i++)
        if (!visited[G[x][i]]) dfs(G[x][i], cur+1);//记得要判断是否遍历过
}

void bfs(int x) {
    memset(visited, false, sizeof(visited));//记得一定要清空
    visited[x] = true;
    q.push(x);
    while (!q.empty()) {
        int v = q.front();
        q.pop();//记得要弹出，否则会一直在第一层遍历
        cout << v << " ";//输出
        for (int i=0; i<G[v].size(); i++) 
            if (!visited[G[v][i]]) {
                visited[G[v][i]] = true;
                q.push(G[v][i]);//记得要入队
            }
    }
}

int main() {
    cin >> n >> m;
    for (int i=1; 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());//标准vector排序
    dfs(1, 0);
    cout << endl;
    bfs(1);
    cout << endl;
    return 0;//完结撒花！
}