SHARE
TWEET

Untitled

a guest Mar 20th, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top