fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <map>
  5. using namespace std;
  6.  
  7. int v = 6; // number of vertices
  8. vector <vector<int>> adjecancy(v + 1); // adjecncy list of the graph
  9.  
  10. void addEdge(int x,int y) //add edge to the graph
  11. {
  12. 	adjecancy[x].push_back(y);
  13. 	//adjecancy[y].push_back(x);
  14. }
  15.  
  16. vector <bool> visited(v + 1);
  17. vector <pair<int, int>> departureSorted(v+1);
  18. int t = 0;
  19.  
  20. void topSort(int v)
  21. {
  22. 	visited[v] = true;
  23.  
  24. 	for (int i : adjecancy[v])
  25. 	{
  26. 		if (!visited[i])
  27. 			topSort(i);
  28. 	}
  29. 	departureSorted[v] = { ++t, v };
  30. }
  31.  
  32. int main()
  33. {
  34. 	ios::sync_with_stdio(false);
  35. 	cin.tie(0); cout.tie(0);
  36.  
  37. 	int n;
  38. 	cin >> n;
  39. 	int x, y;
  40. 	map <int, int> parent;
  41. 	while (n--)
  42. 	{
  43. 		cin >> x >> y;
  44. 		addEdge(x, y);
  45. 	}
  46.  
  47. 	topSort(1);
  48.  
  49. 	//display vectices in topological ordering 
  50. 	sort(departureSorted.begin(), departureSorted.end());
  51. 	for (int i = departureSorted.size()-1; i >= 1; i--)
  52. 		cout << departureSorted[i].second << " ";
  53.  
  54. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
7
1 2
1 4
2 3
1 3
4 6
2 5
5 6
stdout
copy 
1 4 2 5 6 3
https://ideone.com/wPnSgu
language:
C++14 (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!