Advertisement
LA77

Untitled

Feb 25th, 2025
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define FOR(WHATEVER) for(int i = 1; i <= WHATEVER; ++ i)
  5.  
  6. /// INPUT / OUTPUT
  7. const string problem = "ciclueuler";
  8. ifstream fin(problem + ".in");
  9. ofstream fout(problem + ".out");
  10.  
  11. struct graph
  12. {
  13.     int node, edge;
  14. };
  15.  
  16. /// GLOBAL VARIABLES
  17. const ll NMAX = 1e5+5, MOD = 1e9 + 7, INF = 1e9;
  18. int n, m;
  19. bool viz[5 * NMAX];
  20. vector<int>ans;
  21. vector<graph>g[NMAX];
  22.  
  23. /// SOLUTION
  24. inline void dfs(int start)
  25. {
  26.     stack<int>st;
  27.     st.push(start);
  28.     while(!st.empty())
  29.     {
  30.         int node = st.top();
  31.         st.pop();
  32.         if(!g[node].size())
  33.         {
  34.             ans.push_back(node);
  35.         }
  36.         else
  37.         {
  38.             int new_node = g[node].back().node;
  39.             int new_edge = g[node].back().edge;
  40.             g[node].pop_back();
  41.             st.push(node);
  42.             if(!viz[new_edge])
  43.             {
  44.                 viz[new_edge] = 1;
  45.                 st.push(new_node);
  46.             }
  47.         }
  48.     }
  49. }
  50.  
  51. /// READING THE INPUT
  52. int main()
  53. {
  54.     ios::sync_with_stdio(false);
  55.     fin.tie(NULL);
  56.     fout.tie(NULL);
  57.  
  58.     fin >> n >> m;
  59.  
  60.     for(int i = 1; i <= m; ++ i)
  61.     {
  62.         int node1, node2;
  63.         fin >> node1 >> node2;
  64.         g[node1].push_back({node2, i});
  65.         g[node2].push_back({node1, i});
  66.     }
  67.  
  68.     for(int i = 1; i <= n; ++ i)
  69.     {
  70.         if(g[i].size()%2)
  71.         {
  72.             fout << -1;
  73.             return 0;
  74.         }
  75.     }
  76.  
  77.     dfs(1);
  78.     ans.pop_back();
  79.     for(auto x : ans)
  80.         fout << x << ' ';
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement