Advertisement
Guest User

Untitled

a guest
Mar 20th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("O3")
  3. #define count masloriy1489
  4. #define y1 jhgfds
  5. #define ll long long
  6. #define double long double
  7. #define pb push_back
  8. #define eb emplace_back
  9. #define all(v) v.begin(), v.end()
  10. #define rep(i, n) for(int i = 0; i < n; i++)
  11.  
  12. using namespace std;
  13. //freopen("input.txt", "r", stdin);
  14. //freopen("output.txt", "w", stdout);
  15.  
  16. int n, m;
  17. vector<int> a[100001];
  18. int used[100001] = {0};
  19. vector<int> res;
  20. int t = -1;
  21. bool f = false;
  22. bool g = false;
  23.  
  24. void dfs(int x){
  25. used[x] = 1;
  26. if(f)
  27. return;
  28. for(int i : a[x]) {
  29. if(used[i] == 0)
  30. dfs(i);
  31. else if(used[i] == 1){
  32. f = true;
  33. t = i;
  34. res.push_back(x + 1);
  35. return;
  36. }
  37. if(f){
  38. if(!g)
  39. res.push_back(x + 1);
  40. if(x == t)
  41. g = true;
  42. return;
  43. }
  44. }
  45. used[x] = 2;
  46. }
  47.  
  48. int main(){
  49. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  50. freopen("cycle2.in", "r", stdin);
  51. freopen("cycle2.out", "w", stdout);
  52. cin >> n >> m;
  53. int x, y;
  54. for(int i = 0; i < m; i++){
  55. cin >> x >> y;
  56. x--; y--;
  57. if(x == y){
  58. cout << "YES\n" << (x+1);
  59. return 0;
  60. }
  61. a[x].push_back(y);
  62. }
  63. for(int i = 0; i < n; i++){
  64. if (!used[i]) {
  65. dfs(i);
  66. }
  67. }
  68. if(!res.empty()){
  69. cout << "YES\n";
  70. reverse(res.begin(), res.end());
  71. for(int &j : res) {
  72. cout << j << " ";
  73. }
  74. }else{
  75. cout << "NO";
  76. }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement