Cod sursa(job #644383)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 6 decembrie 2011 11:19:39
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <list>
using namespace std;

ifstream fi ("ciclueuler.in");
ofstream fo ("ciclueuler.out");

const int dim = 100005;
int N, M, ce, gr[dim];
list <int> V[dim];

void cit ()
{
	fi >> N >> M;
	for (int i = 0, a, b; i < M; i++)
	{
		fi >> a >> b;
		gr[a]++, gr[b]++;
		V[a].push_back (b);
		V[b].push_back (a);
	}
	for (int i = 1; i <= N; i++)
		if (gr[i] & 1)
		{
			ce = 1;
			return;
		}
}

void sterge (int a, int b)
{
	gr[a]--, gr[b]--;
	V[a].pop_front();
	for (list <int> :: iterator it = V[b].begin(); it != V[b].end(); it++)
		if (*it == a)
		{
			V[b].erase(it);
			return;
		}
}

void euler (int n, int k)
{
	int f;
	while ( !V[n].empty() )
	{
		f = V[n].front();
		sterge (n, f);
		euler (f, k+1);
	}
	if ( !(k == 0 && gr[1] == 0) )
		fo << n << ' ';
}

int main ()
{
	cit ();
	if (ce == 0)
		euler (1, 0);
	else
		fo << "-1";	
	return 0;
}