Cod sursa(job #504384)

Utilizator blastoiseZ.Z.Daniel blastoise Data 27 noiembrie 2010 16:23:46
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>

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

struct tree
{
	int nod;
	tree *link;
}*Graf[100001];

void add(int x,int y)
{
	tree *p;
	
	p=new tree;
	p->nod=x;
	p->link=Graf[y];
	Graf[y]=p;
}

void del(int x,int y)
{
	tree *p,*q;

	p=Graf[x];

	if(y==p->nod)
	{
		q=p;
		Graf[x]=p->link;
		q=NULL;
		return;
	}

	while(p->link)
	{
		if(p->link->nod==y)
		{
			q=p->link;
			p->link=p->link->link;
			q=NULL;
			return;
		}

		p=p->link;
	}
}

void euler(int nod)
{
	tree *p;
	int x;

	p=Graf[nod];

	while(p)
	{
		x=p->nod;
		Graf[nod]=p->link;
		del(x,nod);
		p=NULL;

		euler(x);

		p=Graf[nod];
	}

	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);
		add(x,y);
		add(y,x);
		grad[x]++;
		grad[y]++;
	}

	for(i=1;i<=n;i++)
		if(grad[i]%2==1)
		{
			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;
}