kananasgarli90

round trip

Oct 29th, 2020
679
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int>g[100001];
  4. vector<int>cycle;
  5. int n, m, u, v, color[100001], p[100001], say, end_cycle;
  6. void dfs(int s){
  7.     color[s] = 1;
  8.     for(int i = 0; i < g[s].size() && say != 1; i++){
  9.         u = g[s][i];
  10.         if(color[u] == 0){
  11.             p[u] = s;
  12.             dfs(u);
  13.         }
  14.         else if(color[u] == 1 && p[s] != u){
  15.             say = 1;
  16.             end_cycle = s;
  17.             p[u] = 0;
  18.             break;
  19.         }
  20.     }
  21.     color[s] = 2;
  22. }
  23.  
  24. void printCycle(int s){
  25.     if(s == 0){
  26.         return;
  27.     }
  28.     printCycle(p[s]);
  29.     cycle.push_back(s);
  30. }
  31. int main()
  32. {
  33.     cin>>n>>m;
  34.     while(m--){
  35.         cin>>u>>v;
  36.         g[u].push_back(v);
  37.         g[v].push_back(u);
  38.     }
  39.     for(int i = 1; i <= n; i++){
  40.         if(color[i] == 0){
  41.             dfs(i);
  42.         }
  43.     }
  44.  
  45.     if(say == 1){
  46.         cycle.push_back(end_cycle);
  47.         printCycle(end_cycle);
  48.         cout<<cycle.size()<<endl;
  49.         for(int i = 0; i < cycle.size(); i++){
  50.             cout<<cycle[i]<<" ";
  51.         }
  52.     }
  53.     else{
  54.         cout<<"IMPOSSIBLE"<<endl;
  55.     }
  56. }
  57.  
RAW Paste Data