fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution {
  5.   private: 
  6.     void dfs(int node, vector<int> adj[], int vis[], vector<int> &ls) {
  7.         vis[node] = 1; 
  8.         // traverse all its neighbours
  9.         for(auto it : adj[node]) {
  10.             // if the neighbour is not visited
  11.             if(!vis[it]) {
  12.                 dfs(it, adj, vis, ls); 
  13.             }
  14.         }
  15.         ls.push_back(node); 
  16.     }
  17.  
  18.     void dfs_iter(int node, vector<int> adj[], int vis[], vector<int> &ls) {
  19.          stack<int> s;
  20.          s.push(node);
  21.          vis[node]=1;
  22.          while(!s.empty()){
  23.          	int top = s.top();
  24.         	if(vis[top]){
  25.         		ls.push_back(top);
  26.         		s.pop();
  27.         	}
  28.          	for(auto x: adj[top]){
  29.          		if(!vis[x]){
  30.          			vis[x]=1;
  31.          			s.push(x);
  32.          		}
  33.          	}
  34.  
  35.          }
  36.     }
  37.  
  38.  
  39.  
  40.  
  41.   public:
  42.     // Function to return a list containing the DFS traversal of the graph.
  43.     vector<int> dfsOfGraph(int V, vector<int> adj[]) {
  44.         int vis[V] = {0}; 
  45.         int start = 0;
  46.         // create a list to store dfs
  47.         vector<int> ls; 
  48.         // call dfs for starting node
  49.         // dfs(start, adj, vis, ls); 
  50.         dfs_iter(start, adj, vis, ls); 
  51.         return ls; 
  52.     }
  53. };
  54.  
  55. void addEdge(vector <int> adj[], int u, int v) {
  56.     adj[u].push_back(v);
  57.     adj[v].push_back(u);
  58. }
  59.  
  60. void printAns(vector <int> &ans) {
  61.     for (int i = 0; i < ans.size(); i++) {
  62.         cout << ans[i] << " ";
  63.     }
  64. }
  65.  
  66. int main() 
  67. {
  68.     vector <int> adj[7];
  69.  
  70.     addEdge(adj, 0, 2);
  71.     addEdge(adj, 2, 4);
  72.     addEdge(adj, 0, 1);
  73.     addEdge(adj, 0, 3);
  74.     addEdge(adj, 5, 3);
  75.     addEdge(adj, 1, 6);
  76.  
  77.     Solution obj;
  78.     vector <int> ans = obj.dfsOfGraph(7, adj);
  79.     printAns(ans);
  80.  
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 3 5 1 6 2 4
https://ideone.com/ePU5Q6
language:
C++14 (gcc 8.3)
created:
9 hours 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!