【题目来源】
洛谷：P5318 【深基18.例3】查找文献 - 洛谷
【题目描述】
小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。
假设洛谷博客里面一共有 \(n(n\le 10^5)\) 篇文章（编号为 \(1\) 到 \(n\)）以及 \(m(m\le 10^6)\) 条参考文献引用关系。目前小 K 已经打开了编号为 \(1\) 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。
【输入】
共 \(m+1\) 行，第 \(1\) 行为 \(2\) 个数，\(n\) 和 \(m\)，分别表示一共有 \(n(n\le 10^5)\) 篇文章（编号为 \(1\) 到 \(n\)）以及\(m(m\le 10^6)\) 条参考文献引用关系。
接下来 \(m\) 行，每行有两个整数 \(X,Y\) 表示文章 X 有参考文献 Y。
【输出】
共 \(2\) 行。 第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。
【输入样例】
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
【输出样例】
1 2 5 6 3 7 8 4
1 2 3 4 5 6 7 8
【解题思路】
【算法标签】
《洛谷 P5318 查找文献》 #图论# #图遍历#
【代码详解】
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii; // 定义pair类型保存每条边
const int N=100010; // 数据范围为10^5
int n, m, u, v, vd[N], vb[N]; // 定义vd和vb保存dfs和bfs时，哪些点被访问过
vector<pii> s; // 保存每条边
vector<int> e[N]; // 保存每个点所对应的点bool cmp(const pii a, const pii b) { // 定义排序函数if (a.first == b.first) return a.second<b.second; // 对于起始节点相同的，终止节点按照从小到大排序return a.first<b.first; // 起始节点从小到大排序
}void dfs(int x) { // 定义DFS函数cout << x << " "; // 每找到一个节点，就将这个节点输出vd[x] = 1; // 找到这个节点，就标记已经找过for (int i=0; i<e[x].size(); i++) { // 遍历起始节点x对应的所有终止节点if (!vd[e[x][i]]) dfs(e[x][i]); // 如果没有访问过就访问}return; // 当x没有可访问的终止节点则返回
}void bfs(int x) { // 定义BFS函数queue<int> q; // 定义队列qq.push(x); // 将x压入队列中vb[x] = 1; // 标记已经找过while(!q.empty()) { // 当队列不为空时int k = q.front(); // 获得队列头的节点kq.pop(); // 将队头弹出cout << k << " "; // 输出k，类似DFS输出xfor (int i=0; i<e[k].size(); i++) { // 扫描k节点对应的终止节点if (!vb[e[k][i]]) { // 如果终止节点没有访问过q.push(e[k][i]); // 就将其压入队列中vb[e[k][i]] = 1; // 并将其标记为已访问，避免如1->2，3->2，2被重复压入队列}}}return; // 当队列为空时说明已经访问完毕
}int main()
{cin >> n >> m; // 输入n和mfor (int i=0; i<m; i++) { // 遍历m条边cin >> v >> u; // 输入起始点和终止点s.push_back({v, u}); // 保存到s向量中}sort(s.begin(), s.end(), cmp); // 对边进行排序for (int i=0; i<s.size(); i++) { // 遍历所有的边e[s[i].first].push_back(s[i].second); // 起始节点作为e的下标，保存其对应的终止节点}dfs(1); // 进行DFS查找cout << endl; // 输出换行bfs(1); // 进行BFS查找return 0;
}
【运行结果】
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
1 2 5 6 3 7 8 4
1 2 3 4 5 6 7 8