Cod sursa(job #2758206)

Utilizator KlinashkaDiacicov Calin Marian Klinashka Data 8 iunie 2021 21:34:42
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>
using namespace std;

const int MMAX = (int)5e5;
const int NMAX = (int)1e5;

vector<pair<int, int>> edges;
vector<int> adj[NMAX+1], lst;
bool vis[MMAX+1];

void dfs(int v) {
  while(!adj[v].empty()) {
    int i = adj[v].back(), b;
    adj[v].pop_back();
    if(vis[i] == true) continue;
    b = (edges[i].first == v?edges[i].second:edges[i].first);
    vis[i] = true;
    dfs(b);
  }
  lst.push_back(v);
}

int main() {
  freopen("ciclueuler.in", "r", stdin);
  freopen("ciclueuler.out", "w", stdout);
  int n, m;
  scanf("%d%d", &n, &m);
  for(int i=0;i<m;i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    adj[x].push_back(i);
    adj[y].push_back(i);
    edges.push_back({x, y});
  }
  for(int i=1;i<=n;i++) {
    if((int)adj[i].size()&1) {
      printf("-1\n");
      return 0;
    }
  }
  dfs(1);
  lst.pop_back();
  for(auto e:lst) printf("%d ", e);
  printf("\n");
}