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

将图以邻接列表的方式存储，邻接列表需要排序。
这样 dfs 和 bfs 就可以按照题目要求输出了。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> adj[100001];
int n, m;
bool visited[100001];

void dfs(int u) {
  if (visited[u]) {
    return;
  }
  visited[u] = true;
  cout << u << ' ';
  for (auto v : adj[u]) {
    dfs(v);
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
  }
  for (int i = 1; i <= n; i++) {
    sort(adj[i].begin(), adj[i].end());
  }
  dfs(1);
  cout << endl;
    
  for (int i = 1; i <= n; i++) {
    visited[i] = false;
  }
  queue<int> q;
  visited[1] = true;
  q.push(1);  
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    cout << u << ' ';
    for (auto v : adj[u]) {
      if (visited[v]) {
        continue;
      }
      visited[v] = true;
      q.push(v);
    }
  }
  return 0;
}