Cod sursa(job #2425413)

Utilizator lflorin29Florin Laiu lflorin29 Data 24 mai 2019 19:56:22
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

int main() {
  ifstream cin("ciclueuler.in");
  ofstream cout("ciclueuler.out");

  int n, m;
  cin >> n >> m;
  vector<vector<int>>g(n);
  for(int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  for(int i = 0; i < n; ++i)
    if(g[i].size() % 2) {
      cout << -1;
      return 0;
    }

  vector<int>eulord;
  function<void(int)>euler = [&] (int u) {
    stack<int>stk;
    stk.push(u);
    while(!stk.empty()) {
      int top = stk.top();
      if(g[top].empty()) {
        eulord.push_back(top);
        stk.pop();
      } else {
        int vec = g[top].back();
        g[top].pop_back();
        stk.push(vec);
        g[vec].erase(find(g[vec].begin(), g[vec].end(), top));
      }
    }
  };

  for(int i = 0; i < n; ++i)
    if(!g[i].empty()) euler(i);

  for(auto it = eulord.begin(); it != eulord.end() - 1; ++ it)
    cout << (*it) + 1 << ' ';


}