Cod sursa(job #2417974)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 2 mai 2019 17:13:16
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>

using namespace std;

int n, m;
vector <int> g[100000 + 7];
int sum[500000 + 7];
int ans[500000 + 7], top;
bool went[500000 + 7];

void dfs(int from) {
  while ((int) g[from].size() > 0) {
    int bk = g[from].back();
    g[from].pop_back();
    if (went[bk] == 0) {
      went[bk] = 1;
      int to = sum[bk] - from;
      dfs(to);
    }
  }
  ans[++top] = from;
}

int main() {
  freopen ("ciclueuler.in", "r", stdin);
  freopen ("ciclueuler.out", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--, y--;
    sum[i] = x + y;
    g[x].push_back(i);
    g[y].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    if ((int) g[i].size() & 1) {
      printf("-1\n");
      return 0;
    }
  }
  dfs(1);
  for (int j = 2; j <= top; j++) {
    printf("%d ", ans[j] + 1);
  }
  printf("\n");
  return 0;
}