Cod sursa(job #374377)

Utilizator Mishu91Andrei Misarca Mishu91 Data 16 decembrie 2009 22:12:33
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>

using namespace std;

#define MAX_N 100005
#define MAX_M 200005
#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], St[MAX_M], Rez[MAX_M];

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[++St[0]] = 1; St[0]; )
	{
		int nod = St[St[0]];

		if(!Deg[nod])
		{
			--St[0];
			Rez[++Rez[0]] = nod;
			continue;
		}

		int k = G[nod].back();
		G[nod].pop_back();
		--Deg[k];
		--Deg[nod];
		St[++St[0]] = k;

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

	for(; Rez[0]; --Rez[0])
		fout << Rez[Rez[0]] << " ";
}

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