Cod sursa(job #374574)

Utilizator Mishu91Andrei Misarca Mishu91 Data 17 decembrie 2009 14:20:40
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

#define MAX_N 100005
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

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

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

vector <int> G[MAX_N];

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 solve()
{
	for(int i = 1; i <= N; ++i)
		if(Deg[i] & 1)
		{
			fout << "-1\n";
			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[k];
		--Deg[nod];
		St.push(k);

		foreach(G[k])
			if(*it == nod)
			{
				G[k].erase(it);
				break;
			}
	}

	for(; !Rez.empty(); Rez.pop())
		fout << Rez.top() << " ";
}

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