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

dfs-graph.cpp

// Problem Link: https://practice.geeksforgeeks.org/problems/depth-first-traversal-for-a-graph/1/

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

void DFSRec(vector<int> *G, int s, vector<bool> &visited, vector<int> &vertices) {
  visited[s] = true;
  vertices.push_back(s);
  for(int v: G[s])
    if(!visited[v])
      DFSRec(G, v, visited, vertices);
}


/* Function to do DFS of graph
g : adjacency list of graph
N : number of vertices
return a list containing the DFS traversal of the given graph
*/
vector<int> dfs(vector<int> g[], int N) {
  vector<bool> visited(N, false);
  vector<int> vertices;
  DFSRec(g, 0, visited, vertices);
  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