Cod sursa(job #447536)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 28 aprilie 2010 22:57:48
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <vector>
#include <stack>

#define nmax 100005
#define mmax 500005

#define pb push_back
using namespace std;


vector <int> :: iterator it;
int n, m, a, b, i, ok, L, sol [mmax], frt, node;
vector <int> G [nmax];
stack <int> stv;

int main () {
	freopen ("ciclueuler.in", "r", stdin);
	freopen ("ciclueuler.out", "w", stdout);
	scanf ("%d%d\n", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf ("%d%d\n", &a, &b);
		G [a].pb (b);
		G [b].pb (a);
	}
	for (i = 1; i <= n; i++)
		if (G [i].size () & 1) {
			printf ("-1\n");
			return 0;
		}
	stv.push (1);
	while (stv.size ()) {
		frt = stv.top ();
		node = G [frt].back ();
		G [frt].pop_back ();
		if (G [node].size ()) {
			for (it = G [node].begin (); it != G [node].end (); it++)
				if (*it == frt) {
					G [node].erase (it);
					break;
				}
			stv.push (node);
		} else {
			sol [++L] = stv.top ();
			stv.pop ();
		}
	}
	for (i = 1; i < L; i++)
		printf ("%d ", sol [i]);
	return 0;
}