Cod sursa(job #2286403)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 20 noiembrie 2018 10:32:12
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
const int MAXM = 500005;

struct Edge {
  int x, y;
}e[MAXM];

int gr[MAXN];
vector<int>G[MAXN];
bool viz[MAXM];

int stk[MAXM], top;

void euler(int node) {
  while (gr[node]) {
    stk[++top] = node;
    while (viz[G[node].back()])
      G[node].pop_back();
    int ind = G[node].back();
    int other = e[ind].x ^ e[ind].y ^ node;
    G[node].pop_back();
    viz[ind] = 1;
    gr[node]--;
    gr[other]--;
    node = other;
  }
}

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

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    gr[u]++;
    gr[v]++;
    e[i] = {u, v};
    G[u].push_back(i);
    G[v].push_back(i);
  }

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

  int node = 1;
  printf("%d ", 1);
  while (1) {
    euler(node);
    node = stk[top--];
    if (top == 0)
      break;
    printf("%d ", node);
  }

  return 0;
}