fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define SIZE 100000
  5.  
  6. vector<int> graph[SIZE];
  7.  
  8. int visited[SIZE] = {0};
  9. stack<int> topoOrder;
  10. void toposort(int node) {
  11. 	visited[node] = 1;
  12. 	for(int adj: graph[node]) {
  13. 		if(!visited[adj]) {
  14. 			toposort(adj);
  15. 		}
  16. 	}
  17. 	topoOrder.push(node);
  18. }
  19.  
  20. int main() {
  21. 	int n, m;
  22. 	int indegree[SIZE] = {0};
  23. 	// here n is no of nodes and m is no of edges
  24. 	cin>>n>>m;
  25.  
  26. 	// taking directed edges as input
  27. 	for(int i=0;i<m;i++) {
  28. 		int u, v;
  29. 		cin>>u>>v;
  30. 		graph[u].push_back(v);
  31. 		indegree[v]++;
  32. 	}
  33.  
  34. 	// toposort using dfs
  35. 	printf("Using dfs, Topological Sort: \n");
  36. 	for(int i=1;i<=n;i++) {
  37. 		// we need to call dfs for all disconnected components if present
  38. 		if(!visited[i]) {
  39. 			toposort(i);
  40. 		}
  41. 	}
  42. 	while(!topoOrder.empty()) {
  43. 		printf("%d ", topoOrder.top());
  44. 		topoOrder.pop();
  45. 	}
  46. 	printf("\n");
  47.  
  48. 	// toposort using indegree approach
  49. 	printf("Using in-degree method, Topological Sort: \n");
  50. 	queue<int> q;
  51. 	vector<int> topoOrder2;
  52. 	for(int i=1;i<=n;i++) {
  53. 		if(indegree[i] == 0) {
  54. 			q.push(i);
  55. 		}
  56. 	}
  57.  
  58. 	while(!q.empty()) {
  59. 		int curr = q.front();
  60. 		topoOrder2.push_back(curr);
  61. 		q.pop();
  62.  
  63. 		for(int adj: graph[curr]) {
  64. 			indegree[adj]--;
  65. 			if(indegree[adj] == 0) {
  66. 				q.push(adj);
  67. 			}
  68. 		}
  69. 	}
  70. 	for(int node: topoOrder2) {
  71. 		printf("%d ", node);
  72. 	}
  73. 	printf("\n");
  74.  
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 19064KB
comments (?)
stdin
copy 
6 8
1 2
1 3
2 4
3 4
4 5
3 6
6 5
2 3
stdout
copy 
Using dfs, Topological Sort: 
1 2 3 6 4 5 
Using in-degree method, Topological Sort: 
1 2 3 4 6 5
https://ideone.com/3NFNB1
language:
C++14 (gcc 8.3)
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!