Cod sursa(job #2063017)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 11 noiembrie 2017 00:57:46
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
const int NMAX = 100005;
queue <int> q[NMAX];
int cnt[NMAX];
stack <int> st;
bool vf[NMAX];
int sol[NMAX];

int main() {
  int n, m;
  freopen("ciclueuler.in", "r", stdin);
  freopen("ciclueuler.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    q[x].push(y);
    q[y].push(x);
    ++cnt[x];
    ++cnt[y];
  }
  for(int i = 1; i <= n; ++i) {
    if(cnt[i] % 2) {
      printf("-1\n");
      return 0;
    }
  }
  st.push(1);
  while(!st.empty()) {
    int nod = st.top();
    if(q[nod].size()) {
      int f = q[nod].front();
      q[nod].pop();
      if(!vf[f]) {
        vf[f] = 1;
        st.push(f);
      }
    }
    else {
      st.pop();
      sol[++sol[0]] = nod;
    }
  }
  for(int i = 1; i <= sol[0]; ++i) {
    printf("%d ", sol[i]);
  }
  printf("\n");
  return 0;
}