【题目描述】
小明喜欢翻看博客文章获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小明求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。
假设博客里面一共有 n(n≤10^3) 篇文章(编号为 1 到 n)以及 m(m≤10^4 ) 条参考文献引用关系。目前小明已经打开了编号为 1 的一篇文章,请帮助小明设计一种方法,使小明 可以不重复、不遗漏的看完所有他能看到的文章。 现在已知整理好的参考文献关系图,其中,文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
请对输入的图分别进行 DFS 和 BFS遍历,并输出遍历结果。如果有很多篇文章可以同时参阅,请先看编号较小的那篇。
【输入格式】
第一行两个整数n和m。
接下来m行,每行有两个整数x, y, 表示x有参考文献 y。
【输出格式】
第一行输出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
【样例解释】
输入的样例的文献引用关系的有向图如下所示:
注:代码运用的是与树相关的知识点,未运用图。
#include<bits/stdc++.h>
using namespace std;
struct node {
int data = 0;
int sonnum = 0;
int son[10005];
};
node tree[10005];
int nm[10005] = {0};
void dfs(int p) {
if (nm[p] == 1) {
return;
}
cout << p << ' ';
nm[p] = 1;
sort(tree[p].son + 1, tree[p].son + 1 + tree[p].sonnum);
for (int i = 1; i <= tree[p].sonnum; i++) {
int a = tree[p].son[i];
dfs(a);
}
}
void bfs(int s) {
queue<int> q;
q.push(s);
nm[s] = 1;
cout << s << ' ';
while (!q.empty()) {
int p = q.front();
q.pop();
for (int i = 1; i <= tree[p].sonnum; i++) {
int a = tree[p].son[i];
if (nm[a] == 0) {
cout << a << ' ';
nm[a] = 1;
q.push(a);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
int x, y;
for (int i = 0; i < m;i++) {
cin >> x >> y;
tree[x].sonnum++;
tree[x].son[tree[x].sonnum] = y;
}
dfs(1);
cout << endl;
memset(nm, 0, sizeof(nm));
bfs(1);
cout << endl;
return 0;
}