Cod sursa(job #504419)

Utilizator blastoiseZ.Z.Daniel blastoise Data 27 noiembrie 2010 17:31:06
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <list>

using namespace std;

int i,n,m,x,y,N,stack[500001];

list<int> Graf[100001];

inline void euler(int nod)
{
	list<int>::iterator it,jt;
	int x;

	it=Graf[nod].begin();

	while(it!=Graf[nod].end())
	{
		x=*it;
		jt=Graf[*it].begin();
		while(jt!=Graf[*it].end())
		{
			if(*jt==nod)
			{
				Graf[*it].erase(jt);
				break;
			}
			jt++;
		}
		Graf[nod].pop_front();
		euler(x);
		it=Graf[nod].begin();
	}

	stack[++N]=nod;
}

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

	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		Graf[x].push_back(y);
		Graf[y].push_back(x);
	}

	for(i=1;i<=n;i++)
		if(Graf[i].size()%2)
		{
			printf("-1\n");
			return 0;
		}

	N=0;
	euler(1);

	for(i=N;i>2;i--)
		printf("%d ",stack[i]);
	printf("%d\n",stack[2]);

	return 0;
}