Cod sursa(job #1979335)

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

using namespace std;

const int NMAX = 100000;
const int BUF_SIZE = 4096;
char buf[BUF_SIZE];
int poz = BUF_SIZE;

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

  return buf[poz++];
}

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;
}

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);

  scanf("%d%d", &N, &M);

  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;
  printf("%d ", node);

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

    st.pop();

    if (!st.empty())
      printf("%d ", node);

  }while (!st.empty());

  return 0;
}