Advertisement
btdat2506

Untitled

Aug 22nd, 2020 (edited)
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef int64_t ll;
  6. #define For(i, a, b) for(ll i = a; i <= b; i++)
  7.  
  8. ll n, m, valid, num[100010];
  9. vector <ll> edge[100010], res;
  10.  
  11. void dfs(ll u)
  12. {
  13.     for(ll v: edge[u])
  14.     if (edge[v].size() > 1 && !num[v])
  15.     {
  16.         num[v] = num[u] + 1;
  17.         dfs(v);
  18.         if (valid && *res.end() != *res.begin())
  19.         {
  20.             res.push_back(v);
  21.             return;
  22.         }
  23.         num[v] = 0;
  24.     }
  25.     else
  26.     if (num[u] - num[v] > 2 && res.empty())
  27.     {
  28.         valid = v;
  29.         res.push_back(v);
  30.         res.push_back(u);
  31.         return;
  32.     }
  33. }
  34.  
  35. void process()
  36. {
  37.     For(i, 1, n)
  38.         if (!num[i] && res.empty())
  39.         {
  40.             num[i] = 1;
  41.             dfs(i);
  42.         }
  43.     if (res.empty())
  44.         cout << "IMPOSSIBLE" << "\n";
  45.     else
  46.     {
  47.         cout << res.size() << "\n";
  48.         reverse(res.begin(), res.end());
  49.         for(ll v: res)
  50.         cout << v << ' ';
  51.     }
  52. }
  53.  
  54. void input()
  55. {
  56.     cin >> n >> m;
  57.     For(i, 1, m)
  58.     {
  59.         ll u, v;
  60.         cin >> u >> v;
  61.         edge[u].push_back(v);
  62.         edge[v].push_back(u);
  63.     }
  64. }
  65.  
  66. int main()
  67. {
  68.     /* freopen("test.in", "r", stdin);
  69.     freopen("test.ok", "w", stdout); */
  70.     input();
  71.     process();
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement