BFS of Graph [TC: O(V+E); SC: O(V)]

bfs-graph.cpp

// Problem Link: https://practice.geeksforgeeks.org/problems/bfs-traversal-of-graph/1/

/* Function to do BFS of graph
*  g[]: adj list of the graph
*  N : number of vertices
*/
vector<int> bfs(vector<int> g[], int N) {
  vector<int> vertices;
  vector<bool> visited(N+1, false);
  queue<int> Q;
  visited[0] = true;
  Q.push(0);
  while(not Q.empty()) {
    int u = Q.front(); Q.pop();
    vertices.push_back(u);
    for(int v: g[u])
      if(!visited[v]) {
        visited[v] = true;
        Q.push(v);
      }
  }
  return vertices;
}

int main() {
  int t;  cin >> t;
  while(t--) {
    int vertices, edges, u, v; 
    cin >> vertices >> edges;
    
    // Initialize the graph: G(V, E) -> represented as G[u][v]
    vector<int> G[vertices];
    for(int i = 0; i < edges; ++i) {
      cin >> u >> v;
      G[u].push_back(v);
    }
    
    vector<int> res = bfs(G, vertices);
    for(int i = 0; i < res.size(); ++i) cout << res[i] << " ";
    cout << endl;
  }
  return 0;
}

Problem Link