洛谷 P5318：查找文献 ← DFS BFS

【题目来源】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并输出遍历结果。如果有很多篇文章可以参阅请先看编号较小的那篇因此你可能需要先排序。【输入格式】共 m1 行第 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 91 21 31 42 52 63 74 74 87 8​​​​​​​【输出样例】1 2 5 6 3 7 8 41 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。3DFS 和 BFS 之间要重置 st 数组。4图是有向图 X→Y只加单向边不要加反向边【算法代码】#include bits/stdc.h using namespace std; const int N1e55; vectorint g[N]; bool st[N]; vectorint 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) { queueint q; q.push(u); st[u]true; while(!q.empty()) { int tq.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; cinnm; for(int i1; im; i) { int x, y; cinxy; g[x].push_back(y); } for(int i1; in; i) { sort(g[i].begin(),g[i].end()); } memset(st,false,sizeof st); dfs(1); memset(st,false,sizeof st); bfs(1); for(int i0; idfs_ans.size(); i) { if(i0) cout ; coutdfs_ans[i]; } coutendl; for(int i0; ibfs_ans.size(); i) { if(i0) cout ; coutbfs_ans[i]; } coutendl; 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