Cod sursa(job #2673875)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 17 noiembrie 2020 22:54:21
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>	
#define debug(x) cerr << #x << " " << x << "\n"
#define debugsp(x) cerr << #x << " " << x << " "

using namespace std;

const int INF = 2e9;
const int N = 1e5;
const int M = 5e5;

vector <pair <int, int>> G[1 + N];
stack <int> st;
vector <int> sol;
bool viz[1 + M];

int main() {
  freopen("ciclueuler.in", "r", stdin);
  freopen("ciclueuler.out", "w", stdout);
  int n, m;
  bool ok(true);
  scanf("%d%d", &n, &m);

  for(int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    G[x].push_back(make_pair(y, i));
    G[y].push_back(make_pair(x, i));
  }

  for(int i = 1; i <= n; i++)
    if(G[i].size() & 1)
      ok = false;

  st.push(1);
  while(st.size()) {
    int node = st.top();

    if(G[node].size()) {
      pair <int, int> to = G[node].back();
      G[node].pop_back();

      if(!viz[to.second]) {
        st.push(to.first);
        viz[to.second] = true;
      } 
    } else {
      sol.push_back(node);
      st.pop();
    }
  }

  if(ok == false) printf("-1\n");
  else {
    for(int i = 0; i < sol.size() - 1; i++)
      printf("%d ", sol[i]);
    printf("\n");
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}