Cod sursa(job #1979338)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 10 mai 2017 12:02:46
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <cctype>

using namespace std;

const int NMAX = 100000;
const int BUF_SIZE = 4096;
char buf1[BUF_SIZE];
char buf2[BUF_SIZE];
int poz1 = BUF_SIZE;
int poz2;
char digits[15];

inline char getChar(){
  if (poz1 == BUF_SIZE){
    fread(buf1, 1, BUF_SIZE, stdin);
    poz1 = 0;
  }

  return buf1[poz1++];
}

inline int read(){
  char c;
  do{
    c = getChar();
  } while (!isdigit(c));

  int rez = 0;

  do{
    rez = rez * 10 + c - '0';
    c = getChar();
  } while (isdigit(c));

  return rez;
}

inline void putChar(char c){
  buf2[poz2++] = c;
  if (poz2 == BUF_SIZE){
    fwrite(buf2, 1, BUF_SIZE, stdout);
    poz2 = 0;
  }
}

inline void write(int x){
  int n = 0;
  do{
    int q = x / 10;
    digits[n++] = x - q * 10 + '0';
    x = q;
  } while(x);

  while (n--)
    putChar(digits[n]);
}

inline void flush(){
  fwrite(buf2, 1, BUF_SIZE, stdout);
}

int N, M, node;
vector<int>G[NMAX + 5];
stack<int>st;

void euler(int node){
  while (G[node].size()){
    st.push(node);

    int other = G[node].back();

    G[node].pop_back();
    G[other].erase(find(G[other].begin(), G[other].end(), node));

    node = other;
  }
}
int main(){
  freopen("ciclueuler.in", "r", stdin);
  freopen("ciclueuler.out", "w", stdout);

  N = read();
  M = read();

  while (M--){
    int u = read();
    int v = read();
    G[u].push_back(v);
    G[v].push_back(u);
  }

  bool ok = true;

  for (int i = 1; i <= N; ++i)
    if (G[i].size() & 1){
      ok = false;
      break;
    }

  if (ok == false){
    printf("-1\n");
    return 0;
  }

  node = 1;
  write(node);

  putChar(' ');

  do{
    euler(node);
    node = st.top();

    st.pop();

    if (!st.empty()){
      write(node);
      putChar(' ');
    }

  }while (!st.empty());

  flush();

  return 0;
}