Cod sursa(job #2055493)

Utilizator GoogalAbabei Daniel Googal Data 3 noiembrie 2017 11:55:59
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>

using namespace std;

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

const int nmax = 100000;

struct Edge {
  int to;
  int rev;
  bool del;
};

vector<Edge> g[1 + nmax];
bool mark[1 + nmax];
int start, n, m;
vector<int> sol;

void addedge(int i, int j) {
  int loop = 0;
  if(i == j)
    loop = 1;

  Edge direct  = {j, g[j].size() + loop, false};
  Edge inverse = {i, g[i].size(), false};
  g[i].push_back(direct);
  g[j].push_back(inverse);
  start = i;
}

void bfs() {
  queue < int > q;
  mark[start] = true;
  q.push(start);
  while(!q.empty()){
    int from = q.front();
    q.pop();
    for(int i = 0; i < g[from].size(); i++){
      Edge &e = g[from][i];
      if(mark[e.to] == false){
        mark[e.to] = true;
        q.push(e.to);
      }
    }
  }
}

void eulercircuit(int from) {
  stack < int > st;
  st.push(from);
  while(!st.empty()){
    int from = st.top();
    if(0 < g[from].size()) {
      Edge e = {g[from].back().to, g[from].back().rev, g[from].back().del};
      g[from].pop_back();
      if(e.del == false) {
        g[e.to][e.rev].del = true;
        st.push(e.to);
      }
    } else {
      sol.push_back(from);
      st.pop();
    }
  }
}

int main() {
  in >> n >> m;
  for(int i = 1; i <= m; i++){
    int x, y;
    in >> x >> y;
    addedge(x, y);
  }
  bfs();

  bool hassol = true;
  for(int i = 1; i <= n; i++){
    if(0 < g[i].size()){
      if(mark[i] == false || g[i].size() % 2 == 1)
        hassol = false;
    }
  }

  if(hassol == true) {
    eulercircuit(1);
    for(int i = sol.size()-1; 0 < i; i--)
      out << sol[i] << " ";
  } else {
    out << "-1\n";
  }
  return 0;
}