Cod sursa(job #408438)

Utilizator za_wolfpalianos cristian za_wolf Data 3 martie 2010 02:20:49
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#define NMAX 101000
#define MMAX 501000
int aa[NMAX],bb[NMAX],*w[NMAX],i,j,n,m,k,l,*xx[NMAX],a,s,b,*x[NMAX],y[NMAX],z[NMAX];
struct kkt
{
	int X,Y;
};
kkt q[MMAX];
void euler(int nod)
{
	for (int j=1;j<=x[nod][0];j++)
	{
		i=x[nod][j];
		if (x[nod][j]>0&&i)
		{
			x[nod][j]=0;
			x[i][xx[nod][j]]=0;
			euler(i);
		}
	}
	y[++y[0]]=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",&q[i].X,&q[i].Y);
		aa[q[i].X]++;
		bb[q[i].Y]++;
		z[q[i].X]++;
		z[q[i].Y]++;
	}
	for (i=1;i<=n;i++)
	{
		x[i] = new int [aa[i]+2];
		xx[i]= new int [aa[i]+2];
		x[i][0]=0;
	}

	for (i=1;i<=m;i++)
	{
		x[q[i].X][++x[q[i].X][0]]=q[i].Y;
        if (q[i].X!=q[i].Y)
		x[q[i].Y][++x[q[i].Y][0]]=q[i].X;

		xx[q[i].X][x[q[i].X][0]]=x[q[i].Y][0];
		xx[q[i].Y][x[q[i].Y][0]]=x[q[i].X][0];

	}

	for (i=1;i<=n;i++)
		if (z[a]%2==1)
		{
			printf("-1\n");
			return 0;
		}
	euler(1);
	for (i=y[0];i>=2;i--)
		printf("%d ",y[i]);
	return 0;
}