【题目来源】
https://www.luogu.com.cn/problem/P5318
【题目描述】
小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。
假设洛谷博客里面一共有 n(1≤n≤10^5) 篇文章（编号为 1 到 n）以及 m(1≤m≤10^6) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图，其中，文献 X→Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇（因此你可能需要先排序）。
【输入格式】
共 m+1 行，第 1 行为 2 个数，n 和 m，分别表示一共有 n(1≤n≤10^5) 篇文章（编号为 1 到 n）以及 m(1≤m≤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
【数据范围】
1≤n≤10^5，1≤m≤10^6
【算法分析】
必须注意的坑点：
（1）必须 sort 邻接表：题目要求优先访问小编号节点，不加排序直接 WA。
（2）大数据量一定要写 ios::sync_with_stdio(0); cin.tie(0);，否则 TLE。
（3）DFS 和 BFS 之间要重置 st 数组。
（4）图是有向图 X→Y，只加单向边，不要加反向边！
【算法代码】
#include <bits/stdc++.h> using namespace std; const int N=1e5+5; vector<int> g[N]; bool st[N]; vector<int> dfs_ans,bfs_ans; void dfs(int u) { st[u]=true; dfs_ans.push_back(u); for(int j:g[u]) { if(!st[j]) dfs(j); } } void bfs(int u) { queue<int> q; q.push(u); st[u]=true; while(!q.empty()) { int t=q.front(); q.pop(); bfs_ans.push_back(t); for(int j:g[t]) { if(!st[j]) { st[j]=true; q.push(j); } } } } int main() { int n,m; cin>>n>>m; for(int i=1; i<=m; i++) { int x, y; cin>>x>>y; g[x].push_back(y); } for(int i=1; i<=n; i++) { sort(g[i].begin(),g[i].end()); } memset(st,false,sizeof st); dfs(1); memset(st,false,sizeof st); bfs(1); for(int i=0; i<dfs_ans.size(); i++) { if(i>0) cout<<" "; cout<<dfs_ans[i]; } cout<<endl; for(int i=0; i<bfs_ans.size(); i++) { if(i>0) cout<<" "; cout<<bfs_ans[i]; } cout<<endl; return 0; } /* in: 8 9 1 2 1 3 1 4 2 5 2 6 3 7 4 7 4 8 7 8 out: 1 2 5 6 3 7 8 4 1 2 3 4 5 6 7 8 */
【参考文献】
https://www.luogu.com.cn/problem/solution/P5318
