Cod sursa(job #2734319)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 31 martie 2021 18:22:41
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <vector>

auto *in = fopen("ciclueuler.in", "r"), *out = fopen("ciclueuler.out", "w") ;

const int maxm = 5e5 ;
const int maxn = 1e5 ;

struct DC {
    int dest ;
    int idx ;
};

std::vector<DC> G[1 + maxm] ;

std::bitset<1 + maxn> seenCon ;

void checkCon(int node = 1) {
  seenCon[node] = true ;
  for (auto it : G[node]) {
    if (!seenCon[it.dest]) {
      checkCon(it.dest) ;
    }
  }
}

std::bitset<1 + maxn> seenEuler ;
std::vector<int> solution ;

void getEuler(int node = 1) {
  while (!G[node].empty()) {
    DC top = G[node][0] ;
    G[node].erase(G[node].begin()) ;
    if (!seenEuler[top.idx]) {
      seenEuler[top.idx] = true ;
      getEuler(top.dest) ;
    }
  }
  solution.push_back(node) ;
}

int main() {
  int n, m ;
  fscanf(in, "%d %d", &n, &m) ;
  int x, y ;
  for (int i = 1 ; i <= m ; ++ i) {
    fscanf(in, "%d %d", &x, &y) ;
    G[x].push_back({y, i}) ;
    G[y].push_back({x, i}) ;
  }
  checkCon() ;
  for (int i = 1 ; i <= n ; ++ i) {
    if (G[i].size() % 2 || !seenCon[i]) {
      fprintf(out, "-1") ;
      exit(0) ;
    }
  }
  getEuler() ;
  for (auto it : solution) {
    fprintf(out, "%d ", it) ;
  }
}