Printing Cycle in undirected graph

[problem]
(CSES - Round Trip)

my approach: during dfs maintain a stack, in the stack, put visited node(1) but not finished(2).

whenever we find a node which is already visited and not the parent one. we know there is a cycle and we can iterate through the stack and pop till we found the current one element and print that.

my submission
getting WA in some of the cases.
Any help will be appreciated

submission
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin() , x.end()
#define db double
#define pb push_back
const int mod = (int)1e9+7;
#define f first
#define s second
int n,m;
const int sz = (int)1e7+9;
vector<int>g[sz];
int visit[sz];
int cycle[sz];
vector<int>ans;
stack<int>st;
// #include<ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
 
// typedef tree <int, null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> index_set;
bool res = false;
bool dfs(int u,int p){
    if(!visit[u])st.push(u);
    visit[u] = 1;
    
    if(res)return res;
    for(auto v:g[u])
    {
         if(v==p)continue;
         if(visit[v]==2)continue;
         if(visit[v]==1){
             ans.pb(v);
             while( st.top()!=v){
                 ans.pb(st.top());st.pop();
             }
             ans.pb(v);
             res|=true;
            return res;
         }
 
         if(dfs(v,u))return true; 
 
 
    }
    visit[u] = 2;
    return res;
    
}
 
 
void ok(){
   cin >>  n >> m;
   for(int i=0;i<m;i++)
   {
       int x,y;
       cin >> x >> y;
       g[x].pb(y);
       g[y].pb(x);
   }
bool ans1 = false;
for(int i=1;i<=n;i++){
 
    ans1 = ans1|dfs(i,-1);
 
   if(ans1)
   {   
      cout<<ans.size()<<"\n";
       for(int i=0;i<ans.size();i++){
       cout<<ans[i]<<" ";
      }
      break;
   }
}
 
 
   if(!ans1)
       cout<<"IMPOSSIBLE\n";
   
 
 
}
 
int32_t main() {
    
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
  int t = 1;
  //cin >> t;
  int c = 0;
  while (t--) {
    
    ok();
  }
  return 0;
}
3 Likes

The graph can be disconnected that i saw in last test case, I also implemented by stack and when i got cycle i immediately print it, you can see my soln.

4 Likes

Thank you it helped :slight_smile:

2 Likes