Cod sursa(job #1842964)

Utilizator TimoteiCopaciu Timotei Timotei Data 7 ianuarie 2017 21:01:15
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream> // Algoritmul lui Hierholzer
#include <fstream>
#include <vector>
#include <stack>
#define nMax 100005
using namespace std;
int n, m, x, y, node, new_node;
vector <int> v[nMax], sol;
stack <int> cycle;
void read()
{
    ifstream fin("ciclueuler.in");
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
void write(int ok)
{
  ofstream fout("ciclueuler.out");
  if(ok)
    for(int i = 0; i < sol.size() - 1; ++i)
    fout << sol[i] << ' ';
  else fout << -1;
}
void solve()
{
   for(int i = 1; i <= n; ++i)
    if(v[i].size() % 2 != 0) {write(0); return;}
   cycle.push(1);
   while(!cycle.empty()){
    node = cycle.top();
    if(!v[node].empty()){
        new_node = v[node].back();
        v[node].pop_back();

        for(int i = 0; i < v[new_node].size(); ++i)
        if(v[new_node][i] == node){
            v[new_node].erase(v[new_node].begin() + i);
            break;
        }
        cycle.push(new_node);
        continue;
    }

    sol.push_back(node);
    cycle.pop();
   }
   write(1);
}
int main()
{
    read();
    solve();
    return 0;
}