Problem Description

Little K enjoys browsing Luogu blog articles for knowledge. Each article may have several (or none) reference links pointing to other blog articels. Little K is very curious: if he reads an article, he will certainly read its references (unless he has already read that reference).

Assume there are n (n ≤ 10^5) articles on Luogu blog (numbered from 1 to n) and m (m ≤ 10^6) reference relationships. Little K has already opened article number 1. Help him design a method to read all reachable articles without repetition or omission.

Here is the orgenized reference relationship graph, where X → Y means article X has refeernce Y. It is not guaranteed that article 1 is not referenced by others.

Perform DFS and BFS on this graph and output the traversal order. When there are multiple articles to read, read the one with the smaller number first (so you might need to sort first).

Input Format

• Line 1: two integers n and m.
• Next m lines: each line contains two integers X, Y, indicating article X has reference Y.

Output Format

• Line 1: DFS traversal order.
• Line 2: BFS traversal order.

Sample

Sample Input:

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

Sample Output:

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

Solution

This is a classic problem. The concepts of DFS and BFS are straightforward. The difficulty may lie in ensuring that when multiple articles can be read, the one with the smaller number is read first, and that no article is missed or repeated. The former can be handled by using a set (which automatically sorts and removes duplicates), and the latter by using a visited array.

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<set<int>>& adj, vector<int>& visited, int node) {
    for (int son : adj[node]) {
        if (visited[son] == 0) {
            cout << son << " ";
            visited[son] = 1;
            dfs(adj, visited, son);
        }
    }
}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<set<int>> adj(n + 1);
    vector<int> visited(n + 1, 0);
    while (m--) {
        int a, b;
        cin >> a >> b;
        adj[a].insert(b);
    }
    cout << 1 << " ";
    visited[1] = 1;
    dfs(adj, visited, 1);
    cout << endl;
    fill(visited.begin(), visited.end(), 0);
    bfs(adj, visited, 1);
    return 0;
}

Here, the relationship between nodes is represented as an adjacency list where adj[i] contains all nodes that i points to, similar to an adjacency matrix.