SHARE
TWEET

print cycle

kananasgarli90 Jun 5th, 2020 847 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma comment(linker,"/STACK:1000000000");
  4. vector<int>v[100001];
  5. int color[100001], p[100001], endCycle, cycle;
  6. void dfs(int s){
  7.     color[s] = 1;
  8.     for(int i = 0; i < v[s].size(); i++){
  9.         if(cycle == 1){
  10.             return;
  11.         }
  12.         int u = v[s][i];
  13.         if(color[u] == 0){
  14.             p[u] = s;
  15.             dfs(u);
  16.         }
  17.         else if(color[u] == 1){
  18.             p[u] = -1;
  19.             endCycle = s;
  20.             cycle = 1;
  21.             break;
  22.         }
  23.     }
  24.     color[s] = 2;
  25. }
  26. void printCycle(int s){
  27.     if(s == -1){
  28.         return;
  29.     }
  30.     printCycle(p[s]);
  31.     cout<<s<<" ";
  32. }
  33. int main()
  34. {
  35.     int n, m, a, b;
  36.     cin>>n>>m;
  37.     while(m--){
  38.         cin>>a>>b;
  39.         v[a].push_back(b);
  40.     }
  41.     for(int i = 1; i <= n; i++){
  42.         if(color[i] == 0){
  43.             dfs(i);
  44.         }
  45.     }
  46.     if(cycle == 1){
  47.         cout<<"YES"<<endl;
  48.         printCycle(endCycle);
  49.     }
  50.     else{
  51.         cout<<"NO"<<endl;
  52.     }
  53. }
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