fork download 
  1. // { Driver Code Starts
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  // } Driver Code Ends
  6.  
  7.  
  8. class Solution 
  9. {
  10.     public:
  11. 	//Function to return a list containing the DFS traversal of the graph.
  12. 	vector<int>dfsOfGraph(int V, vector<int> adj[])
  13. 	{
  14. 	    vector<int> res;
  15. 	    bool to_visit[V];
  16. 	    for(int i=0;i<V;i++){
  17. 	        to_visit[i]=true;
  18. 	    }
  19. 	    stack<int> stack1,stack2;
  20. 	    stack1.push(0);
  21. 	    to_visit[0]=false;
  22. 	    while(!(stack1.empty())){
  23. 	        int x=stack1.top();
  24. 	        res.push_back(x);
  25. 	        stack1.pop();
  26. 	        for(auto iter:adj[x]){
  27. 	            if(to_visit[iter]){
  28. 	                stack2.push(iter);
  29. 	                to_visit[iter]=false;
  30. 	            }
  31. 	            while(!stack2.empty()){
  32. 	                x=stack2.top();
  33. 	                stack1.push(x);
  34. 	                stack2.pop();
  35. 	            }
  36. 	        }
  37. 	    }
  38. 	    return res;
  39. 	}
  40. };
  41.  
  42. // { Driver Code Starts.
  43. int main(){
  44. 	int tc;
  45. 	cin >> tc;
  46. 	while(tc--){
  47. 		int V, E;
  48.     	cin >> V >> E;
  49.  
  50.     	vector<int> adj[V];
  51.  
  52.     	for(int i = 0; i < E; i++)
  53.     	{
  54.     		int u, v;
  55.     		cin >> u >> v;
  56.     		adj[u].push_back(v);
  57.     		adj[v].push_back(u);
  58.     	}
  59.         // string s1;
  60.         // cin>>s1;
  61.         Solution obj;
  62.         vector<int>ans=obj.dfsOfGraph(V, adj);
  63.         for(int i=0;i<ans.size();i++){
  64.         	cout<<ans[i]<<" ";
  65.         }
  66.         cout<<endl;
  67. 	}
  68. 	return 0;
  69. }  // } Driver Code Ends
Success #stdin #stdout 0.01s 5524KB
comments (?)
stdin 
1
5 4
0 1
0 2
0 3
2 4
stdout 
0 3 2 4 1
https://ideone.com/0VH64o
language:
C++14 (gcc 8.3)
created:
4 years 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!