【洛谷习题】P5318 【深基18.例3】查找文献
2023-02-18 16:42:43 时间
题目描述
小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。
假设洛谷博客里面一共有 n(n<10^6)条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章,请帮助小 K 设计一种方法,使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图,其中,文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
请对这个图分别进行 DFS 和 BFS,并输出遍历结果。如果有很多篇文章可以参阅,请先看编号较小的那篇(因此你可能需要先排序)。
输入格式
无
输出格式
无
解题思路
一道标准的遍历图问题,并且需要用dfs和bfs两种方式实现。而节点数在10^5范围,用邻接矩阵存储会超,所以存储改用vector数组。
完整代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int n, m;
int seen[10005]; //是否读过该博客
vector<int> lines[10005];
void dfs(int thisIdx) {
if (seen[thisIdx] == 1)return;
cout << thisIdx << " ";
seen[thisIdx] = 1;
for (int i = 0; i < lines[thisIdx].size(); i++) {
dfs(lines[thisIdx][i]);
}
}
bool pushNode(queue<int> &que,int val) {
if (seen[val] == 1)return false;
que.push(val);
seen[val] = 1;
return true;
}
void bfs(int thisIdx) {
queue<int> que;
pushNode(que, thisIdx);
while (que.empty() == false) {
int tmp = que.front();
que.pop();
cout << tmp << " ";
for (int i = 0; i < lines[tmp].size(); i++) {
pushNode(que, lines[tmp][i]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t1, t2;
cin >> n >> m;
//读入箭头
for (int i = 1; i <= m; i++) {
cin >> t1 >> t2;
lines[t1].push_back(t2);
}
//排序箭头
for (int i = 1; i <= n; i++)
sort(lines[i].begin(),lines[i].end());
dfs(1);
cout << endl;
memset(seen, '\0', sizeof(seen));
bfs(1);
cout << endl;
return 0;
}
相关文章
- (三)《数字电子技术基础》——码制
- (六)STM32基础——独立按键
- [C语言] 常量与变量
- (七)STM32基础——C语言知识复习
- [C语言] 猜数字小游戏「功能优化」
- (八)STM32——时钟系统介绍
- 如何应对新员工对工作提出的各种建议?
- [C语言] 初始字符串 & 转义字符与注释
- (二)算法基础——递归(1)
- 软件测试知识小课堂之Bug激活率
- (九)STM32——Systemlnit初始化函数讲解
- [C语言] 初始函数 & 数组
- (十)51单片机——利用蜂鸣器播放《孤勇者》(附成果展示)
- [C语言] 一维数组
- (四)《数字电子技术基础》——逻辑代数基础
- NE555 & 工作模式介绍
- 电路模型和电路定律(Ⅰ)
- (三)算法基础——递归(2)
- 虚拟现实 VR 碰撞 3D 可视化,图扑打造一体化管控平台
- 电路模型和电路定律(Ⅱ)