Cod sursa(job #504327)

Utilizator blastoiseZ.Z.Daniel blastoise Data 27 noiembrie 2010 15:04:32
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>

int pos,i,x,y,n,m,gr[100001],stack[500001];

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

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

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

	p=T[x];
	q=NULL;

	while(p)
	{
		if(p->nod==y)
			if(q==NULL)
			{
				T[x]=p->link;
				break;
			}
			else
			{
				q->link=p->link;
				break;
			}
		q=p;
		p=p->link;
	}
}

void euler(int nod)
{
	tree *p;
	int x;
	
	p=T[nod];
	
	while(p)
	{
		x=p->nod;
		T[nod]=p->link;
		delnod(p->nod,nod);
		euler(x);
		p=T[nod];
	}

	stack[++pos]=nod;
}

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

	scanf("%d%d",&n,&m);
	
	for(i=1;i<=n;i++) gr[i]=0;

	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		addnod(x,y);
		addnod(y,x);
		gr[x]++;
		gr[y]++;
	}

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

	pos=0;
	euler(1);

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

	return 0;
}