Cod sursa(job #2417410)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 29 aprilie 2019 18:12:00
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;
const int MAXM = 500000;

struct Edge {
  int u, v;
  int other(int x) {
    return u ^ v ^ x;
  }
}e[MAXM + 5];

vector<int>G[MAXN + 5];
int gr[MAXN + 5];
bool viz[MAXM + 5];
int stk[MAXM + 5], top;

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

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);
    e[i] = {u, v};
    gr[u]++;
    gr[v]++;
    G[u].push_back(i);
    G[v].push_back(i);
  }

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

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

  return 0;
}