Cod sursa(job #1998537)

Utilizator GoogalAbabei Daniel Googal Data 8 iulie 2017 12:40:48
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

const int nmax = 100000;

struct Edge {
  int to;
  int rev; //indicele muchiei opuse in g[to]. g[to][rev] e muchia opusa
  bool del;
};

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

//la aceasta reprezentare trebuie sa fim atenti la muchii din nod in acelasi nod
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) {
  for(int i = 0; i < g[from].size(); i++){
    Edge &e = g[from][i];
    if(e.del == false){
      e.del = true;
      g[e.to][e.rev].del = true;
      //cout<<from<<" -> "<<e.to<<endl;
      eulercircuit(e.to);
    }
  }
  sol.push_back(from);
}

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(start);
    for(int i = sol.size()-1; 0 < i; i--)
      out << sol[i] << " ";
  } else {
    out << "-1\n";
  }
  return 0;
}