Advertisement
Guest User

a

a guest
Jun 18th, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int n, m, pp[100005];
  8. vector<int> adj_lst[100005];
  9. bool vis[100005];
  10.  
  11. bool cyclic(int v, int parent) {
  12.     vis[v]=1;
  13.     for(int i : adj_lst[v]) {
  14.         if(!vis[i]) {
  15.             pp[i] = v;
  16.             return cyclic(i, v);
  17.         }
  18.         else if(i != parent) {
  19.             int ct=2;
  20.             int j = v;
  21.             while(j != i) {
  22.                 ct++;
  23.                 j=pp[j];
  24.             }
  25.             cout << ct << endl;
  26.             cout << i+1 << " ";
  27.             j = v;
  28.             while(j != i) {
  29.                 cout << j+1 << " ";
  30.                 j=pp[j];
  31.             }
  32.             cout << i+1 << endl;
  33.             return 1;
  34.         }
  35.     }
  36.     return 0;
  37. }
  38.  
  39. bool cyclic() {
  40.     for(int i = 0; i < n; i++) {
  41.         if(!vis[i]) if(cyclic(i, -1)) return 1;
  42.     }
  43.     return 0;
  44. }
  45.  
  46. int main()
  47. {
  48.     // freopen("in.txt", "r", stdin);
  49.     cin >> n >> m;
  50.     for(int i = 0; i < m; i++) {
  51.         int x, y;
  52.         cin >> x >> y;
  53.         x--; y--;
  54.         adj_lst[x].push_back(y);
  55.         adj_lst[y].push_back(x);
  56.     }
  57.     if(cyclic()) {
  58.         // alexander lukashenko
  59.     } else {
  60.         cout << "IMPOSSIBLE" << endl;
  61.     }
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement