Cod sursa(job #498873)

Utilizator Addy.Adrian Draghici Addy. Data 7 noiembrie 2010 15:51:45
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <cstdio>
#include <list>
#include <stack>
#include <queue>

using namespace std;

#define NMAX 100050

int grad[NMAX], viz[NMAX], n, m, i, x, y, nod;
list <int> G[NMAX], E;
queue <int> Q;
stack <int> S;

int eulerian (); void ciclu (int);

int main () {
	
	freopen ("ciclueuler.in", "r", stdin);
	freopen ("ciclueuler.out", "w", stdout);
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		grad[x]++, grad[y]++;
		G[x].push_back (y), G[y].push_back (x);
	}
	
	if (eulerian ()) {
		
		nod = 1;
		do {
			ciclu (nod);
			nod = S.top (), S.pop ();
			E.push_back (nod);
		} while (!S.empty ());
		
		for (list <int>::iterator it = E.begin (); it != E.end (); it++)
			printf ("%d ", *it);
	}
	else
		printf ("-1");
	
	return 0;
}

int eulerian () {
	
	int nod;
	list <int>::iterator it;
	
	Q.push (1), viz[1] = 1;
	while (!Q.empty ()) {
		nod = Q.front (), Q.pop ();
		for (it = G[nod].begin (); it != G[nod].end (); it++)
			if (!viz[*it])
				Q.push (*it), viz[*it] = 1;
	}
	
	for (i = 1; i <= n; i++)
		if (!viz[i] || grad[i] % 2) return 0;
	
	return 1;
}

void sterge (int x, int y) {
	
	list <int>::iterator it;
	
	grad[x]--, grad[y]--;
	G[x].pop_front ();
	for (it = G[y].begin (); it != G[y].end (); it++)
		if (*it == x) {
			G[y].erase (it);
			return;
		}
}

void ciclu (int nod) {
	
	int fiu;
	
	while (!G[nod].empty ()) {
		fiu = G[nod].front ();
		S.push (nod);
		sterge (nod, fiu);
		nod = fiu;
	}
}