fork(7) download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <unordered_set>
  4. #include <vector>
  5. #include <stack>
  6. using namespace std;
  7.  
  8. unordered_map<int, unordered_set<int>> g;
  9.  
  10. void addEdge(int x, int y) {
  11. 	g[x].insert(y);
  12. }
  13.  
  14. void topSort() {
  15. 	unordered_set<int> visited;
  16. 	stack<int> mainStack;
  17.  
  18. 	for(auto it = g.begin(); it != g.end(); it++) {
  19. 		if(visited.count(it->first) == 0) {
  20. 			visited.insert(it->first);
  21. 			stack<int> locStack;
  22. 			locStack.push(it->first);
  23. 			while(!locStack.empty()) {
  24. 				int curr = locStack.top();
  25. 				bool unVisCh = false;
  26. 				for(auto it2 = g[curr].begin(); it2 != g[curr].end(); it2++) {
  27. 					int child = *it2;
  28. 					if(visited.count(child) == 0) {
  29. 						unVisCh = true;
  30. 						visited.insert(child);
  31. 						locStack.push(child);
  32. 					}
  33. 				}
  34. 				if(!unVisCh) {
  35. 					locStack.pop();
  36. 					mainStack.push(curr);
  37. 				}
  38. 			}
  39. 		}
  40. 	}
  41.  
  42. 	while(!mainStack.empty()) {
  43. 		cout<<mainStack.top()<<" ";
  44. 		mainStack.pop();
  45. 	}
  46. 	cout<<endl;
  47. }
  48.  
  49. int main() {
  50. 	addEdge(1,2);
  51. 	addEdge(4,5);
  52. 	addEdge(5,6);
  53. 	addEdge(3,2);
  54. 	addEdge(2,6);
  55. 	addEdge(1,3);
  56. 	addEdge(4,3);
  57.  
  58. 	topSort();
  59.  
  60. 	return 0;
  61. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4 5 1 3 2 6
https://ideone.com/r6Pl4r
language:
C++14 (clang 8.0)
created:
6 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!