Cod sursa(job #2055408)

Utilizator GoogalAbabei Daniel Googal Data 3 noiembrie 2017 10:36:26
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#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;
};

int n, m, start;
bool mark[1 + NMAX];

vector < Edge > g[1 + NMAX];
vector < int > sol;


void addedge(int x, int y) {
  int loop = 0;
  if(x == y)
    loop = 1;

  Edge direct = {y, g[y].size() + loop, false};
  Edge inverse = {x, g[x].size(), false};

  g[x].push_back(direct);
  g[y].push_back(inverse);
  start = x;
}

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++) {
      int to = g[from][i].to;
      if(mark[to] == false) {
        mark[to] = true;
        q.push(to);
      }
    }
  }
}

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

void finalize() {
  in.close();
  out.close();
}

void eulercircuit(int start) {
  stack < int > st;
  st.push(start);

  while(!st.empty()) {
    int from = st.top();
    int k = 0;

    for(int i = 0; i < g[from].size(); i++) {
      Edge &e = g[from][i];
      if(e.del == false) {
        k++;
        e.del = true;
        g[e.to][e.rev].del = true;
        st.push(e.to);
        break;
      }
    }

    if(k == 0) {
      sol.push_back(from);
      st.pop();
    }
  }
}

void write() {
  for(int i = sol.size() - 1; i > 0; i--) {
    out << sol[i] << ' ';
  }
}

void solve() {
  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;
        break;
      }
    }
  }

  if(hassol == true) {
    eulercircuit(1);
    write();
    finalize();
  } else {
    out << "-1\n";
    finalize();
    exit(EXIT_SUCCESS);
  }

}

int main()
{
  read();
  bfs();
  solve();
  return 0;
}