Cod sursa(job #2417971)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 2 mai 2019 17:10:18
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <vector>

using namespace std;

int n, m;
vector <vector <int>> g;
vector <pair <int, int>> way;
vector <int> ans;
vector <bool> went;

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 = way[bk].first + way[bk].second - from;
      dfs(to);
    }
  }
  ans.push_back(from);
}

int main() {
  freopen ("ciclueuler.in", "r", stdin);
  freopen ("ciclueuler.out", "w", stdout);
  scanf("%d %d", &n, &m);
  g.resize(n);
  way.resize(m);
  went.resize(m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--, y--;
    way[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 = 1; j < (int) ans.size(); j++) {
    printf("%d ", ans[j] + 1);
  }
  printf("\n");
  return 0;
}