fork(2) download
  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
stdin
4 4
1 4
4 3
3 2
4 2
stdout
1 4 3 2