tien_noob

Chu trình euler

Mar 3rd, 2021 (edited)
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <numeric>
  4. #include <set>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <climits>
  9. #include <string>
  10. #include <cstdio>
  11. #include <cmath>
  12. #define task "TESTCODE"
  13. using namespace std;
  14. struct T
  15. {
  16.     int node, id;
  17. };
  18. vector<vector<T>> Adj;
  19. bool b[400001];
  20. int n, m, x, y;
  21. vector<int> V;
  22. void read()
  23. {
  24.     cin >> n >> m;
  25.     Adj.resize(n + 1);
  26.     for (int i = 1; i <= m; ++ i)
  27.     {
  28.         cin >> x >> y;
  29.         Adj[x].push_back({y, i});
  30.         Adj[y].push_back({x, i});
  31.         b[i] = true;
  32.     }
  33. }
  34. void solve()
  35. {
  36.     V.push_back(1);
  37.     while (!V.empty())
  38.     {
  39.         int u = V.back();
  40.         bool deleted = false;
  41.         while (!Adj[u].empty() && b[Adj[u].back().id] == false)
  42.         {
  43.             Adj[u].pop_back();
  44.         }
  45.         if (!Adj[u].empty())
  46.         {
  47.             V.push_back(Adj[u].back().node);
  48.             b[Adj[u].back().id] = false;
  49.             Adj[u].pop_back();
  50.         }
  51.         if (u == V.back())
  52.         {
  53.             cout << V.back() << ' ';
  54.             V.pop_back();
  55.         }
  56.     }
  57. }
  58. /// TLE, I don't know why, how the da fuq did that happen
  59. int main()
  60. {
  61.    ios_base::sync_with_stdio(false);
  62.    cin.tie(nullptr);
  63.    //freopen(task".INP", "r", stdin);
  64.    //freopen(task".OUT", "w", stdout);
  65.    read();
  66.    solve();
  67. }
  68.  
Add Comment
Please, Sign In to add comment