参考文献(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;
}

相关推荐

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 13:50:03       171 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 13:50:03       189 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 13:50:03       157 阅读
  4. Python语言-面向对象

    2024-07-20 13:50:03       170 阅读

热门阅读

  1. C?C++?

    2024-07-20 13:50:03       30 阅读
  2. ArcGIS Pro SDK (九)几何 10 弧

    2024-07-20 13:50:03       27 阅读
  3. AB测试介绍

    2024-07-20 13:50:03       36 阅读
  4. MULESOFT

    MULESOFT

    2024-07-20 13:50:03      36 阅读
  5. libevent的事件分发相关接口

    2024-07-20 13:50:03       35 阅读
  6. 082、Python 读文本文件

    2024-07-20 13:50:03       37 阅读
  7. Linux绑定硬件IRQ到指定CPU核

    2024-07-20 13:50:03       34 阅读
  8. 使用内网穿透工具 frp 发布内网 web 站点

    2024-07-20 13:50:03       37 阅读
  9. 【WebRTC】Duplex通信是什么意思?

    2024-07-20 13:50:03       36 阅读
  10. TCP Socket编程示例

    2024-07-20 13:50:03       36 阅读