fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<vector<int> > graph;
  7.  
  8. enum color_t {
  9. 	white = 0,
  10. 	gray,
  11. 	black
  12.  
  13. };
  14.  
  15. vector<color_t> color;
  16.  
  17. vector<int> topologic_sort;
  18.  
  19. void dfs (int v) {
  20. 	if (color[v] != white)
  21. 		return;
  22.  
  23. 	color[v] = gray;
  24. 	for (auto next: graph[v])
  25. 		dfs(next);
  26.  
  27. 	color[v] = black;
  28. 	topologic_sort.push_back(v+1);
  29. }
  30.  
  31. int main() {
  32. 	int n,m;
  33. 	while (true)
  34. 	{
  35. 		cin >> n >> m;
  36.  
  37. 		if (n==0 && m==0)
  38. 			break;
  39.  
  40. 		graph.resize(n);
  41.  
  42. 		color.resize(n,white);
  43.  
  44. 		//topologic_sort.resize(n);
  45.  
  46. 		while (m--)
  47. 		{
  48. 			int i,j;
  49. 			cin >> i >> j;
  50. 			i--; j--;
  51. 			graph[i].push_back(j);
  52. 		}
  53.  
  54.  
  55. 		//dfs(0);
  56.  
  57. 		for (int i = 0; i<n; ++i)
  58. 		{
  59. 			if (color[i] == white)
  60. 				dfs(i);
  61. 		}
  62.  
  63. 		//cout << topologic_sort[0] << endl;
  64.  
  65. 		reverse(topologic_sort.begin(), topologic_sort.end());
  66.  
  67. 		for (auto el : topologic_sort)
  68. 		{
  69. 			cout << el << " ";
  70. 		}
  71.  
  72. 		cout << endl;
  73.  
  74. 		graph.clear();
  75. 		color.clear();
  76. 		topologic_sort.clear();
  77.  
  78.  
  79. 	}
  80.  
  81.  
  82. 	return 0;
  83. }
Success #stdin #stdout 0s 5368KB
comments (?)
stdin
copy 
6 6
1 2
3 2
4 2
2 5
6 5
4 6
3 1
3 2
0 0
stdout
copy 
4 6 3 1 2 5 
3 2 1
https://ideone.com/1zBnTL
Порядок задач ( топологическая сортировка )
language:
C++14 (gcc 8.3)
created:
2 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!