参考文献（C++）

【题目描述】

小明喜欢翻看博客文章获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小明求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设博客里面一共有 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;
}

原文地址：https://blog.csdn.net/qxh10/article/details/140564866

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！