fork(3) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #define WHITE 0
  5. #define GREY 1
  6. #define BLACK 2
  7. using namespace std;
  8.  
  9. bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size)
  10. {
  11. 	state[v] = GREY;
  12. 	for (int i = 0; i < vertex[v].size(); i++)
  13. 	{
  14. 		int dest = vertex[v].at(i);
  15. 		if (state[dest] == WHITE)
  16. 		{
  17. 			if (dfs(dest, vertex, state, result, size))
  18. 				return true;
  19. 		}
  20. 		else if (state[dest] == GREY)
  21. 		{
  22. 			return true;
  23. 		}
  24. 	}
  25. 	state[v] = BLACK;
  26. 	result.push_back(v+1);
  27. 	return false;
  28. }
  29.  
  30. void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)
  31. {
  32. 	for (int i = 0; i < size; i++)
  33. 	{
  34. 		if (state[i] == WHITE)
  35. 		{
  36. 			bool cyclic = dfs(i, vertex, state, result, size);
  37. 			if (cyclic)
  38. 			{
  39. 				result.clear();
  40. 				result.push_back(-1);
  41. 				return;
  42. 			}
  43. 		}
  44. 	}
  45. 	reverse(result.begin(), result.end());
  46. }
  47.  
  48. int main() 
  49. {
  50. 	ios::sync_with_stdio(false);
  51. 	int n, m;
  52. 	cin >> n >> m;
  53. 	vector<int> vertex[n];
  54. 	int state[n];
  55. 	vector<int> result;
  56. 	fill (state, state + n, WHITE);
  57. 	for (int i = 0; i < n; i++)
  58. 	{
  59. 		int begin, end;
  60. 		cin >> begin >> end;
  61. 		vertex[begin-1].push_back(end-1);
  62. 	}
  63. 	topologicalSort(vertex, state, result, n);
  64. 	for (int i = 0; i < result.size(); i++)
  65. 		cout << result.at(i) << " ";
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 3412KB
comments (?)
stdin
copy 
4 4
1 4
4 3
3 2
4 2
stdout
copy 
1 4 3 2
https://ideone.com/E2Q2EZ
Топологическая сортировка http://w...content-available-to-author-only...p.com/ru/problems/4003
language:
C++14 (gcc 8.3)
created:
8 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!