fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. vector<int> bfsTraversal(int N, const vector<pair<int, int>>& edges) {
  9.     vector<vector<int>> adjList(N);
  10.     vector<int> visitedOrder;
  11.     vector<bool> visited(N, false);
  12.  
  13.     for (const auto& edge : edges) {
  14.         int u = edge.first;
  15.         int v = edge.second;
  16.         adjList[u].push_back(v);
  17.     }
  18.  
  19.     for (auto& neighbors : adjList) {
  20.         sort(neighbors.begin(), neighbors.end());
  21.     }
  22.  
  23.     queue<int> q;
  24.     q.push(0);
  25.     visited[0] = true;
  26.  
  27.     while (!q.empty()) {
  28.         int current = q.front();
  29.         q.pop();
  30.         visitedOrder.push_back(current);
  31.  
  32.         for (int neighbor : adjList[current]) {
  33.             if (!visited[neighbor]) {
  34.                 visited[neighbor] = true;
  35.                 q.push(neighbor);
  36.             }
  37.         }
  38.     }
  39.  
  40.     return visitedOrder;
  41. }
  42.  
  43. int main() {
  44.     int T;
  45.     cin >> T;
  46.  
  47.     while (T--) {
  48.         int N, E;
  49.         cin >> N >> E;
  50.  
  51.         vector<pair<int, int>> edges;
  52.         for (int i = 0; i < E; i++) {
  53.             int u, v;
  54.             cin >> u >> v;
  55.             edges.emplace_back(u, v);
  56.         }
  57.  
  58.         vector<int> result = bfsTraversal(N, edges);
  59.  
  60.         for (size_t i = 0; i < result.size(); i++) {
  61.             if (i != 0) cout << " ";
  62.             cout << result[i];
  63.         }
  64.         cout << endl;
  65.     }
  66.  
  67.     return 0;
  68. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Z1DLfz
language:
C++14 (clang 8.0)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!