Advertisement
Guest User

8_6

a guest
Jun 17th, 2019
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5. #include <deque>
  6. #include <algorithm>
  7. #include <bitset>
  8. #include <cstring>
  9. #include <math.h>
  10. #include <string>
  11. #include <set>
  12. #include <iomanip>
  13. #include <bitset>
  14. #include <random>
  15. #include <complex>
  16. #include <random>
  17. #include <cassert>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20. using namespace std;
  21. #define pb push_back
  22. #define ll long long
  23. #define mp make_pair
  24. #define fdeg firdeg
  25. #define snd second
  26. #define ins insert
  27. #define ld long double
  28. #define mt make_tuple
  29. #define fst first
  30. const double PI = acos(-1);
  31. // = 5e5 + 17;
  32. ll MOD = 1e9 + 7;
  33. const int INF = 1e9;
  34. const int MaXN = 105;
  35. const int N = 1e6 + 1000;
  36. const int maxlog = 18;
  37. ld ecr = 1e-8;
  38. vector<int> g[N];
  39. vector<int> topsort;
  40. bool used[N];
  41. int cl[N];
  42. int start , c_end;
  43. bool has_cycle (int u)
  44. {
  45. cl[u] = 1;
  46. for (auto v: g[u])
  47. {
  48. if (!cl[v])
  49. {
  50. if (has_cycle(v))
  51. {
  52. return true;
  53. }
  54. }
  55. else if (cl[v] == 1)
  56. {
  57. start = u;
  58. c_end = v;
  59. return true;
  60. }
  61. }
  62. cl[u] = 2;
  63. return false;
  64. }
  65.  
  66. void dfs(int u)
  67. {
  68. used[u] = 1;
  69. for(auto v : g[u])
  70. {
  71. if(!used[v]) dfs(v);
  72. }
  73. topsort.pb(u);
  74. }
  75. signed main()
  76. {
  77. ios_base::sync_with_stdio(0);
  78. cin.tie(0);
  79. cout.tie(0);
  80. int n , m;
  81. cin >> n >> m;
  82. start = INF;
  83. for(int i = 0; i < m; i++)
  84. {
  85. int u , v;
  86. cin >> u >> v;
  87. u--, v--;
  88. g[u].pb(v);
  89. }
  90. for (int i = 0; i < n; i++)
  91. {
  92. if (has_cycle(i))
  93. {
  94. break;
  95. }
  96. }
  97. if(start < INF)
  98. {
  99. cout << -1 << "\n";
  100. return 0;
  101. }
  102. for(int i = 0; i < n; i++)
  103. {
  104. if(!used[i])
  105. {
  106. dfs(i);
  107. }
  108. }
  109. reverse(topsort.begin(), topsort.end());
  110. for(auto u : topsort)
  111. {
  112. cout << u + 1 << " ";
  113. }
  114. return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement