Cod sursa(job #2375785)

Utilizator GoogalAbabei Daniel Googal Data 8 martie 2019 12:08:20
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>

using namespace std;

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

const int NMAX = 1e5;

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

int n, m, start;

bitset < 1 + NMAX > mark;

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] = 1;
  q.push(start);

  while(!q.empty()) {
    int from = q.front();
    q.pop();

    for(Edge to : g[from]) {
      if(mark[to.to] == 0) {
        mark[to.to] = 1;

        q.push(to.to);
      }
    }
  }
}

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

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

    if(0 < g[from].size()) {
      Edge e = g[from].back();
      g[from].pop_back();

      if(e.del == false) {
        st.push(e.to);
        g[e.to][e.rev].del = true;
      }
    } 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 ok = true;

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

  if(ok == true) {
    eulercircuit(1);

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

    out << '\n';
  } else {
    out << "-1\n";
  }

  in.close();
  out.close();

  return 0;
}