Cod sursa(job #1354940)

Utilizator valiro21Valentin Rosca valiro21 Data 22 februarie 2015 11:05:11
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <list>
#include <stack>
#include <vector>
#include<algorithm>

#define NMax 100001

using namespace std;

stack<int> s;
list<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, w;
    for (s.push (1); !s.empty ();) {
        now = s.top ();
        if (!v[now].empty ()) {
            w = *(v[now].begin ());

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

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

int main()
{
    freopen( "ciclueuler.in", "rt", stdin);
    freopen( "ciclueuler.out", "wt", stdout);

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

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

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

    return 0;
}