Cod sursa(job #1414066)

Utilizator toranagahVlad Badelita toranagah Data 2 aprilie 2015 12:21:17
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
//Problem euler
#include <cassert>
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

#define len(c) (int)(c).size()
#define pb push_back
#define mp make_pair
#define x first
#define y second
typedef vector<int> VI;
typedef pair<int, int> PII;

int N, M;
vector<VI> graph;
vector<PII> edges;
vector<VI::iterator> git;
vector<bool> vis;
VI sol;


int other(int n, int e) {
  return edges[e].x + edges[e].y - n;
}

void euler(int node) {
  while (git[node] != end(graph[node])) {
    int edge = *git[node];
    advance(git[node], 1);

    if (!vis[edge]) {
      vis[edge] = 1;
      euler(other(node, edge));
    }
  }

  sol.pb(node);
}

int main() {
  fin >> N >> M;

  graph.resize(N + 1);
  git.resize(N + 1);
  edges.resize(M);
  
  for (int i = 0, a, b; i < M; i += 1) {
    fin >> a >> b;
    graph[a].pb(i);
    graph[b].pb(i);
    edges[i] = mp(a, b);
  }
  vis.resize(len(edges));

  for (int i = 1; i <= N; i += 1) {
    if (len(graph[i]) & 1) {
      fout << -1 << endl;
      return 0;
    }
    git[i] = begin(graph[i]);
  }

  euler(1);

  sol.pop_back();
  for (auto v: sol) {
    fout << v << ' ';
  }
  fout << endl;

  return 0;
}