Cod sursa(job #406966)

Utilizator Mishu91Andrei Misarca Mishu91 Data 1 martie 2010 22:21:14
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

#define foreach(V) for(vector <int> :: iterator it = (V).begin(); it != (V).end(); ++it)

const int MAX_N = 100005;

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

int N, M, Deg[MAX_N];
vector <int> G[MAX_N];
stack <int> St, Rez;

void citire()
{
	fin >> N >> M;
	
	for(int i = 1; i <= M; ++i)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
		
		++Deg[x];
		++Deg[y];
	}
}

void ciclueuler()
{
	for(int i = 1; i <= N; ++i)
		if(Deg[i] & 1)
		{
			fout << "-1";
			return;
		}
		
	for(St.push(1); !St.empty();)
	{
		int nod = St.top();
		
		if(!Deg[nod])
		{
			St.pop();
			Rez.push(nod);
			continue;
		}
		
		int k = G[nod].back();
		G[nod].pop_back();
		--Deg[nod];
		--Deg[k];
		St.push(k);
		
		foreach(G[k])
			if(*it == nod)
			{
				G[k].erase(it);
				break;
			}
	}
	
	Rez.pop();
	for(; !Rez.empty(); Rez.pop())
		fout << Rez.top() << " ";
}

int main()
{
	citire();
	ciclueuler();
}