Cod sursa(job #2574877)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 6 martie 2020 10:26:37
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define NMAX 100000
#define MMAX 500000

using namespace std;

struct elem {
  int nod, ind;

  elem(int nnod = 0, int iind = 0) {
    nod = nnod, ind = iind;
  }
};

int n, m;
int uz[MMAX + 5];
vector<int> st;
vector<elem> v[NMAX + 5];

int main() {
  freopen("ciclueuler.in", "r", stdin);
  freopen("ciclueuler.out", "w", stdout);
  int x, y;

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

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

  st.push_back(1);
  while(st.size()) {
    x = st.back();
    while(v[x].size() && uz[v[x].back().ind])
      v[x].pop_back();

    if(v[x].size()) {
      y = v[x].back().nod;
      uz[v[x].back().ind] = 1;
      st.push_back(y);
      v[x].pop_back();
    }
    else {
      if(st.size() > 1)
        printf("%d ", x);
      st.pop_back();
    }
  }

  return 0;
}