Cod sursa(job #522616)

Utilizator invatacelTudorache Marius invatacel Data 15 ianuarie 2011 16:34:45
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <utility>

using namespace std;

int n,m;
vector<pair<int,int> > V[1<<17];
int ind[1<<17];
vector<int> ciclu;
stack<int> ST;

int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);

	scanf ("%d%d",&n,&m);

	for (int i=0;i<m;i++)
	{
		int a,b;
		scanf ("%d%d",&a,&b);
		ind[a]++;ind[b]++;
		if (a == b)
		{
			V[a].push_back(make_pair(a,V[a].size()+1));
			V[a].push_back(make_pair(a,V[a].size()-1));
		}
		else
		{
			V[a].push_back(make_pair(b,V[b].size()));
			V[b].push_back(make_pair(a,V[a].size()-1));
		}
	}

	for (int i=1;i<=n;i++)
		if (ind[i]&1)
		{
			printf ("-1\n");
			return 0;
		}

	ST.push(1);

	while (ST.size() > 0)
	{
		int node = ST.top();

		while (V[node].size() > 0 && V[node].back().first < 0) V[node].pop_back();

		if (V[node].size() > 0)
		{
			pair<int,int> much = V[node].back();

			ST.push(much.first);
			V[much.first][much.second].first = -1;
			ind[node]--;
			ind[much.first]--;
			V[node].pop_back();
		}
		else
		{
			ciclu.push_back(node);
			ind[node] = -1;
			ST.pop();
		}
	}

	for (int i=1;i<=n;i++)
		if (ind[i] != -1)
		{
			printf ("-1\n");
			return 0;
		}

	for (size_t i=0;i<ciclu.size()-1;i++)
		printf ("%d ",ciclu[i]);
	printf ("\n");
	return 0;
}