remember_Me

Untitled

Aug 5th, 2020
1,205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x)                x.begin(),x.end()
  3. #define pb                    push_back
  4. #define IOfast                ios_base::sync_with_stdio(false); cin.tie(NULL);
  5. using namespace std;
  6.  
  7. int visited[(int)2e5 + 1];
  8. vector <int> graph[(int)2e5 + 1];
  9. vector<int> path; // to keep track of paths
  10.  
  11. void dfs(int node,int par)
  12. {
  13.   visited[node] = 1;
  14.   path.pb(node);
  15.   for(auto &next:graph[node])
  16.   {
  17.     if(par == next) continue;
  18.  
  19.     if(visited[next])
  20.     {
  21.        path.pb(next);
  22.        int i = (find(all(path),next) - path.begin());
  23.        cout<<path.size() - i<<"\n";
  24.  
  25.        while(i<path.size())
  26.          cout<<path[i++]<<" ";
  27.  
  28.        exit(0);
  29.     }
  30.     else
  31.       dfs(next,node);
  32.   }
  33.   path.pop_back();
  34. }
  35.  
  36. void solve()
  37. {
  38.   int n,m,u,v;
  39.   cin>>n>>m;
  40.  
  41.   while(m--)
  42.     cin>>u>>v , graph[u].pb(v) , graph[v].pb(u);
  43.  
  44.  for(int i = 1;i<=n;i++)
  45.     if(visited[i] == 0)
  46.        dfs(i,0);
  47.  
  48.  cout<<"IMPOSSIBLE";
  49. }
  50.  
  51. int main()
  52. {
  53.   IOfast;
  54.   solve();
  55.  
  56.   return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment