Cod sursa(job #1354950)

Utilizator valiro21Valentin Rosca valiro21 Data 22 februarie 2015 11:14:00
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <list>
#include <stack>
#include <vector>
#include <algorithm>

#define NMax 100001

using namespace std;

stack<int> s;
vector<int> v[NMax];
vector<int> cycle;
int n, m, x, y;

bool isEuler () {
    for (int i = 1; i <= n; i++)
        if (v[i].size () & 1)
            return 0;
    return 1;
}

void euler (int now) {
    int last;
    for (s.push (now); !s.empty ();) {
        now = s.top ();
        if (!v[now].empty ()) {
            int last = v[now].back ();

            v[now].pop_back ();
            v[last].erase ( find (v[last].begin (), v[last].end (), now) );

            s.push (last);
        }
        else {
            s.pop ();
            cycle.push_back (now);
        }
    }
}

int main()
{
    ifstream fin("ciclueuler.in");
    ofstream fout("ciclueuler.out");

    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> x >> y,
        v[x].push_back (y),
        v[y].push_back (x);

    if (!isEuler ()) {
        fout << -1;
        return 0;
    }

    euler (1);
    for (int i = 0; i < cycle.size () - 1; i++)
        fout << cycle[i] << ' ';

    return 0;
}