fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int int64_t
  4. #define ll long long
  5. #define el endl;
  6. #define be begin()
  7. #define en end()
  8. #define sz(x) (int)x.size()
  9. #define all(n) n.begin(), n.end()
  10. #define rall(n) n.rbegin(), n.rend()
  11. const int mod = 998244353, INF = 0x3f3f3f3f, N = 1e3 + 5;
  12. int R4[] = {1, 0, -1, 0};
  13. int C4[] = {0, 1, 0, -1};
  14. int R8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
  15. int C8[] = {-1,  0,  1, -1, 1, -1, 0, 1};
  16.  
  17. void RUN()
  18. {
  19.     ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  20.     #ifndef ONLINE_JUDGE
  21.     freopen("input.txt", "r", stdin);
  22.     freopen("output.txt", "w", stdout);
  23.     #endif
  24. }
  25.  
  26. template <typename T> istream& operator>> (istream& in, vector <T> &v)
  27. {
  28.     for (auto &i : v) in >> i;
  29.     return in;
  30. }
  31.  
  32. void solve()
  33. {
  34.     int n, m; cin >> n >> m;
  35.     vector<vector<int>> adj(n + 1);
  36.     for (int i = 0; i < m; i++) 
  37.     {
  38.         int x, y; cin >> x >> y;
  39.         adj[x].push_back(y);
  40.         adj[y].push_back(x);
  41.     }
  42.  
  43.     vector<int> vis(n + 1, 0);
  44.     vector<int> path;
  45.     bool f = 0;
  46.     int val;
  47.  
  48.     function <bool(int, int)> DFS = [&](int u, int p) -> bool
  49.     {
  50.         vis[u] = 1;
  51.  
  52.         for (auto &i : adj[u])
  53.         {
  54.             if (!vis[i])
  55.             { 
  56.                 if (DFS(i, u))
  57.                 {
  58.                     path.push_back(i); return 1;
  59.                 }
  60.             }
  61.             else if (vis[i] && i != p)
  62.             {
  63.                 val = i;
  64.                 path.push_back(i);
  65.                 return 1;
  66.             }
  67.         }
  68.     };
  69.  
  70.     for (int i = 1; i <= n; i++)
  71.     {
  72.         if (!vis[i])
  73.             if (DFS(i, -1)) f = 1;
  74.         if (f) break;
  75.     }
  76.  
  77.     if (!f) cout << "IMPOSSIBLE" << '\n';
  78.     else
  79.     {
  80.         int c = 0;
  81.         for (auto &i : path)
  82.         {
  83.             if (c < 2) cout << i << ' ';
  84.             if (i == val) c++;
  85.         }
  86.         if (c != 2) cout << val << '\n';
  87.     }
  88. }
  89.  
  90. int32_t main()
  91. {
  92.     RUN();
  93.  
  94.     int T = 1;
  95.     // cin >> T;
  96.     while (T--) solve();
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/V3PtWh
language:
C++14 (gcc 8.3)
created:
15 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!