Advertisement
btdat2506

Untitled

Aug 23rd, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 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. bool ck()
  12. {
  13.     if (!res.empty())
  14.     if (res[0] != res[res.size() - 1])
  15.     return 1;
  16.     return 0;
  17. }
  18.  
  19. void dfs(ll u)
  20. {
  21.     for(ll v: edge[u])
  22.     if (!num[v])
  23.     {
  24.         num[v] = num[u] + 1;
  25.         dfs(v);
  26.         if (valid && ck())
  27.         {
  28.             res.push_back(u);
  29.             return;
  30.         }
  31.         else
  32.         if (valid) return;
  33.         num[v] = 0;
  34.     }
  35.     else
  36.     if (num[u] - num[v] > 1 && res.empty())
  37.     {
  38.         valid = v;
  39.         res.push_back(v);
  40.         res.push_back(u);
  41.         return;
  42.     }
  43. }
  44.  
  45. void process()
  46. {
  47.     For(i, 1, n)
  48.         if (!num[i] && res.empty())
  49.         {
  50.             num[i] = 1;
  51.             dfs(i);
  52.         }
  53.     if (res.empty())
  54.         cout << "IMPOSSIBLE" << "\n";
  55.     else
  56.     {
  57.         cout << res.size() << "\n";
  58.         //reverse(res.begin(), res.end());
  59.         for(ll v: res)
  60.         cout << v << ' ';
  61.     }
  62. }
  63.  
  64. void input()
  65. {
  66.     cin >> n >> m;
  67.     For(i, 1, m)
  68.     {
  69.         ll u, v;
  70.         cin >> u >> v;
  71.         edge[u].push_back(v);
  72.         edge[v].push_back(u);
  73.     }
  74. }
  75.  
  76. int main()
  77. {
  78.     /* freopen("test.in", "r", stdin);
  79.     freopen("test.ok", "w", stdout); */
  80.     input();
  81.     process();
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement