Advertisement
AdelKhalilov

Untitled

Jul 9th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4.  
  5. using namespace std;
  6.  
  7. int n, m;
  8. vector <int> g[100010];
  9. int color [100010];
  10. bool fl = false;
  11. stack <int> st1;
  12. stack <int> st2;
  13.  
  14. void dfs (int v)
  15. {
  16. color[v] = 1;
  17. st1.push(v);
  18. for (int i = 0; i < g[v].size() ; i++)
  19. {
  20. if (fl) break;
  21.  
  22. int u = g[v][i];
  23. if (color[u] == 0)
  24. {
  25. dfs(u);
  26. }
  27. else
  28. {
  29. if (color[u] == 1)
  30. {
  31. fl = true;
  32. int k = st1.top();
  33. st1.pop();
  34. st2.push(k);
  35. while (k != u)
  36. {
  37.  
  38. k = st1.top();
  39. st1.pop();
  40. st2.push(k);
  41. }
  42. }
  43. }
  44. }
  45. color[v] = 2;
  46. if (!st1.empty())
  47. {
  48. st1.pop();
  49. }
  50. }
  51.  
  52. int main()
  53. {
  54. cin >> n >> m;
  55. for (int i = 0; i < m; i++)
  56. {
  57. int a, b;
  58. cin >> a, b;
  59. g[a - 1].push_back(b - 1);
  60. }
  61.  
  62. for (int i = 0; i < n; i++)
  63. {
  64. color[i] = 0;
  65. }
  66.  
  67. for (int i = 0; i < n; i++)
  68. {
  69. if (fl) break;
  70. if (color[i] == 0)
  71. {
  72. dfs(i);
  73. }
  74. }
  75. if (!fl)
  76. {
  77. cout << "NO";
  78. }
  79. else
  80. {
  81. cout << "YES" << endl;
  82. while (!st2.empty())
  83. {
  84. cout << st2.top() << " ";
  85. st2.pop();
  86. }
  87. }
  88. return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement