fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Graph{
  5. 	public:
  6. 	int n, m;
  7. 	vector<vector<int>> adj;
  8.  
  9. 	Graph(int nodes): adj(nodes){
  10. 		n = nodes;
  11. 		m = 0;
  12. 	}
  13.  
  14. 	void addEdge(int u, int v){
  15. 		adj[u].push_back(v);
  16. 		++m;
  17. 	}
  18.  
  19. 	void dfs(int u, vector<bool> &visited, stack<int> &st, bool &useStack){
  20. 		visited[u] = true;
  21. 		cout<<u<<" ";
  22.  
  23. 		for(auto adjNode: adj[u]){
  24. 			if(!visited[adjNode]){
  25. 				dfs(adjNode, visited, st, useStack);
  26.  
  27. 				if(useStack){
  28. 					st.push(adjNode);
  29. 				}
  30. 			}
  31. 		}
  32. 	}
  33.  
  34. 	void findRoute(){
  35. 		vector<bool> visited(n, false);
  36. 		stack<int> st;
  37.  
  38. 		bool useStack = true;
  39.  
  40. 		cout<<"DFS: ";
  41. 		for(int i=0; i<n; ++i){
  42. 			if(!visited[i]){
  43. 				dfs(i, visited, st, useStack);
  44. 				st.push(i);
  45. 			}
  46. 		}
  47.  
  48. 		cout<<"\nThe topological sort: ";
  49. 		while(!st.empty()){
  50. 			int u = st.top();
  51.  
  52. 			cout<<u;
  53.  
  54. 			st.pop();
  55.  
  56. 			if(!st.empty())
  57. 				cout<<" ";
  58. 		}
  59.  
  60. 	}
  61.  
  62. 	void printGraph(){
  63. 		cout<<"The adjacency list,\n"; 
  64. 		for(int i=0; i<n; ++i){
  65. 			cout<<"Node "<<i<<": ";
  66. 			for(auto node:adj[i])
  67. 				cout<<"->"<<node;
  68. 			cout<<"\n";
  69. 		}
  70. 	}
  71. };
  72.  
  73. int main()
  74. {
  75. 	int n; 
  76.  
  77. 	cin>>n;
  78.  
  79. 	Graph g(n);
  80.  
  81. 	cin>>n;
  82.  
  83. 	int inp, inp2;
  84.  
  85. 	for(int i=0; i<n; ++i){
  86. 		cin>>inp>>inp2;
  87. 		g.addEdge(inp, inp2);
  88. 	}
  89.  
  90. 	g.printGraph();
  91.  
  92. 	cout<<"----------------------------------\n";
  93.  
  94. 	g.findRoute();
  95.  
  96. 	return 0;
  97. }
  98.  
  99.  
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
6
6
5 2
5 0
4 0
4 1
2 3
3 1
stdout
copy 
The adjacency list,
Node 0: 
Node 1: 
Node 2: ->3
Node 3: ->1
Node 4: ->0->1
Node 5: ->2->0
----------------------------------
DFS: 0 1 2 3 4 5 
The topological sort: 5 4 2 3 1 0
https://ideone.com/EYw1ut
Topological sort of directed acyclic graph || Time complexity: O(n+m)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!