Cod sursa(job #2734323)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 31 martie 2021 18:26:34
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.34 kb
#include <iostream>
#include <vector>
#include <bitset>

#ifndef InputReader_H
#define InputReader_H

#include <cstdio>

template <typename T>
class InputReader {
private:
    FILE *input_file ;
    static const int SIZE = (1 << 17) ;
    int point ;
    char buffer[SIZE] ;
    __attribute__ ( (always_inline)) void advance() {
      ++ point ;
      if (point == SIZE) {
        point = 0 ;
        fread (buffer, SIZE, 1, input_file) ;
      }
    }
public:
    InputReader() {}
    InputReader (const char *file_name) {
      input_file = fopen (file_name, "r") ;
      point = 0 ;
      fread (buffer, SIZE, 1, input_file) ;
    }
    __attribute__ ( (always_inline)) InputReader &operator >> (T &n) {
      for (; !isdigit (buffer[point]) ; advance()) ;
      n = 0 ;
      for (; isdigit (buffer[point]) ; advance()) {
        n = n * 10 + buffer[point] - '0' ;
      }
      return *this ;
    }
} ;

#endif //UNTITLED1_LIBRARY_H

//
// Created by Euraba on 03.03.2021.
//

#ifndef OUTPARSING_H
#define OUTPARSING_H


#include <ios>
#include <fstream>

class OutputParsing {
public:
    OutputParsing() {} ;

    OutputParsing(const char * file_name) {
      output_file.open(file_name, std::ios::out | std::ios::binary) ;
      output_file.sync_with_stdio(false) ;
      index = 0 ;
    }

    inline OutputParsing & operator << (int target) {
      aux = 0 ;
      n = target ;
      target < 0 ? sign = -1 : sign = 1 ;
      if (!n) {
        nr[aux ++] = '0' ;
      }
      for ( ; n ; n /= 10) {
        nr[aux ++] = sign * (n % 10) + '0' ;
      }
      if (sign == -1) {
        buffer[index] = '-' ;
        inc() ;
      }
      for ( ; aux ; inc())
        buffer[index] = nr[-- aux] ;
      return *this ;
    }

    inline OutputParsing & operator << (const char * target) {
      aux = 0 ;
      while (target[aux]) {
        buffer[index] = target[aux ++] ;
        inc() ;
      }
      return *this ;
    }
    ~OutputParsing() {
      output_file.write(buffer, index) ;
      output_file.close() ;
    }

private:
    std::fstream output_file;
    static const int SIZE = 0x200000;
    int index = 0, aux, n, sign;
    char buffer[SIZE], nr[24];

    inline void inc() {
      if (++index == SIZE) {
        index = 0 ;
        output_file.write(buffer, SIZE);
      }
    }
} ;


#endif //OUTPARSING_H

InputReader<int> in ("ciclueuler.in") ;
OutputParsing out ("ciclueuler.out") ;

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 + maxm> 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 ;
  in >> n >> m ;
  int x, y ;
  for (int i = 1 ; i <= m ; ++ i) {
    in >> 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]) {
      out << "-1" ;
      exit(0) ;
    }
  }
  getEuler() ;
  for (auto it : solution) {
    out << it << " " ;
  }
}