Cod sursa(job #504412)

Utilizator blastoiseZ.Z.Daniel blastoise Data 27 noiembrie 2010 17:13:14
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <set>

using namespace std;

multiset<int> Graf[100001];

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

inline void euler(int nod)
{
	multiset<int>::iterator it,jt;
	int x=0;
	
	it=Graf[nod].begin();

	while(it!=Graf[nod].end())
	{
		x=*it;
		jt=Graf[*it].find(nod);
		if(jt!=Graf[*it].end()) Graf[*it].erase(jt);
		Graf[nod].erase(Graf[nod].begin());
		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].insert(y);
		Graf[y].insert(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;
}