图的遍历 —— 洛谷 [深基18.例3] 查找文献

编程基础 • 2025-03-06 14:30 • 阅读 17

【深基18.例3】查找文献

题目描述

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

假设洛谷博客里面一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$ ）以及 $m(m\le10^6)$ 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

输入格式

共 $m + 1$ 行，第 1 行为 2 个数， $n$ 和 $m$ ，分别表示一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$ ）以及 $m(m\le10^6)$ 条参考文献引用关系。

接下来 $m$ 行，每行有两个整数 $X, Y$ 表示文章 X 有参考文献 Y。

输出格式

共 2 行。
第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。

样例 #1

样例输入 #1

样例输出 #1

1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8

这是一道典题。DFS和BFS的概念不必多说。如果事先知道这两个概念，那么可能有难度的地方可能在于如何在有很多篇文章可以参阅时，先看编号较小的那篇，同时要做到不重不漏。不过这两者解决并不困难：前者只需要利用STL中的set容器（自动排序去重），后者利用哈希表记录是否参阅过即可。

题解如下：

#include<bits/stdc++.h>
using namespace std;
vector<int> num;
const int N = 100001;
void dfs(vector<set<int>>& reference,int node){
   
    for(int son : reference[node]){
   
        if(num[son] == 0){
   
            cout << son << " ";
            num[son] = 1;
            dfs(reference,son);
        }
    }
}

void bfs(vector<set<int>>& reference,int node){
   
    queue<int> q;
    q.push(node);
    while(!q.empty()){
   
        int now = q.front();
        q.pop();
        if(num[now] == 0){
   
            cout << now << " ";
            num[now] = 1;
            for(int son : reference[now]){
   
                q.push(son);
            }
        }
    }
}


int main(){
   
    int n,m;
    cin >> n >> m;
    vector<set<int>> reference(N);
    num = vector<int>(N,0);
    while(m--){
   
        int a,b;
        cin >> a >> b;
        reference[a].insert(b);
    }
    cout << 1 << " ";
    num[1] = 1;
    dfs(reference,1);
    cout << endl;
    num = vector<int>(N,0);
    bfs(reference,1);
    return 0;
}

这里用来说明节点与节点之间的关系并没有和通常一样构建node节点。reference[i]里面的元素均为i指向的元素，颇有邻接矩阵的意思。

感谢你能看到这里。