Cod sursa(job #280169)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 13 martie 2009 11:24:44
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
const long NMAX=100010;
const long MMAX=500010;
long *a[NMAX], x[MMAX], y[MMAX], d[NMAX], q[NMAX], n, m, vf, st[MMAX];
bool viz[NMAX];

void euler(long v);
void bf(long nod);

int main()
{
	long i;
	freopen("ciclueuler.in", "r", stdin);
	freopen("ciclueuler.out", "w", stdout);
	scanf("%ld%ld", &n, &m);
	for (i=0; i<m; i++)
	{
		scanf("%ld%ld", &x[i], &y[i]);
		d[x[i]]++;
		d[y[i]]++;
	}//for i
	i=1;
	while (i<=n)
	{
		if (d[i]%2)
		{
			printf("-1");
			return 0;
		}//if
		i++;
	}//while
	for (i=1; i<=n; i++)
	{
		a[i]=new long[d[i]];
		a[i][0]=0;
	}//for i
	for (i=0; i<m; i++)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		a[y[i]][++a[y[i]][0]]=x[i];
	}//for i
	bf(1);
	i=1;
	while (i<=n)
	{
		if (!viz[i])
		{
			printf("-1");
			return 0;
		}//if
		i++;
	}//while
	euler(1);
	return 0;
}//main

void euler(long v)
{
	long i, w;
	st[vf++]=v;
	while (vf>0)
	{
		v=st[vf-1];
		i=1;
		while ((!a[v][i])&&(i<a[v][0]))
			i++;
		if (a[v][i])
		{
			w=a[v][i];
			d[v]--;
			a[v][i]=0;
			i=1;
			while ((a[w][i]!=v)&&(i<a[w][0]))
				i++;
			if (a[w][i]==v)
			{
				a[w][i]=0;
				d[w]--;
			}//if
			st[vf++]=w;
		}//if
		else
		{
			if (vf>1)
				printf("%ld ", st[vf-1]);
			vf--;
		}//else
	}//while
}//euler

void bf(long nod)
{
	long u=0, p=0, i;
	q[u++]=nod;
	viz[nod]=1;
	while (u!=p)
	{
		nod=q[p++];
		for (i=1; i<=a[nod][0]; i++)
			if (!viz[a[nod][i]])
			{
				q[u++]=a[nod][i];
				viz[a[nod][i]]=1;
			}//if
	}//while
}//bf