Advertisement
Guest User

Untitled

a guest
Jun 17th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void dfs(long long v, vector<long long>* gr, vector<bool>& used, vector<long long>& an)
  4. {
  5. used[v] = true;
  6. for (long long i = 0; i < gr[v].size(); i++)
  7. {
  8. long long flag = gr[v][i];
  9. if (!used[flag])
  10. dfs(flag, gr, used, an);
  11. }
  12. an.push_back(v + 1);
  13. }
  14. void topSort(long long n, vector<long long>* gr, vector<bool>& used, vector<long long>& an)
  15. {
  16. for (long long i = 0; i < n; i++)
  17. used[i] = false;
  18. for (long long i = 0; i < n; i++)
  19. if (!used[i])
  20. dfs(i, gr, used, an);
  21. reverse(an.begin(), an.end());
  22. }
  23. bool checky(long long v, long long& checkys, vector<long long>* gr, vector<long long>& color)
  24. {
  25. color[v] = 1;
  26. for (size_t i = 0; i < gr[v].size(); i++)
  27. {
  28. long long flag = gr[v][i];
  29. if (color[flag] == 0)
  30. {
  31. if (checky(flag, checkys, gr, color))
  32. return true;
  33. }
  34. else if (color[flag] == 1)
  35. {
  36. checkys = flag;
  37. return true;
  38. }
  39. }
  40. color[v] = 2;
  41. return false;
  42. }
  43. int main()
  44. {
  45. long long n, m;
  46. cin >> n >> m;
  47. long long a, b;
  48. vector<long long> gr[n + 1];
  49. vector<bool> used(n);
  50. vector<long long> an;
  51. vector<long long> color(n, 0);
  52. long long checkys = -1;
  53. for (long long i = 0; i < m; i++)
  54. {
  55. cin >> a >> b;
  56. gr[a - 1].push_back(b - 1);
  57. }
  58. for (long long i = 0; i < n; i++)
  59. {
  60. if (checky(i, checkys, gr, color))
  61. break;
  62. }
  63. if (checkys != -1)
  64. cout << "-1";
  65. else
  66. {
  67. topSort(n, gr, used, an);
  68. for (long long i = 0; i < an.size(); i++)
  69. {
  70. cout << an[i] << " ";
  71. }
  72. cout << endl;
  73. }
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement