Cod sursa(job #1201058)

Utilizator heracleRadu Muntean heracle Data 24 iunie 2014 13:38:11
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>

//FILE* in=fopen("ciclueuler.in","r");
//FILE* out=fopen("ciclueuler.out","w");

int nod,muc;
const int Q=502001,W=100001;

struct muchie
{
	int x,y;
	bool f;
} v[Q];

int urm[2*Q],val[2*Q],lst[W],nr;

void add(int t)
{
	nr++;
	val[nr]=t;
	urm[nr]=lst[v[t].x ];
	lst[v[t].x]=nr;

	nr++;
	val[nr]=t;
	urm[nr]=lst[v[t].y];
	lst[v[t].y]=nr;
}

void euler(int act)
{
	int p,m;
	p=lst[act];

	while(p!=0)
	{
		m=val[p];

		if(v[m].f==0)
		{
			v[m].f=1;
			
			if(v[m].x==act)
				euler(v[m].y);
			else
				euler(v[m].x);
		}

		p=urm[p];
	}
	printf("%d ",act);


}

int numar[W];

int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d%d",&nod,&muc);

	int a,b;

	for(int i=1; i<=muc; i++)
	{
		scanf("%d%d",&v[i].x,&v[i].y);
		numar[v[i].x]++;
		numar[v[i].y]++;
		add(i);
	}
	for(int i=1; i<=nod; i++)
	{
		if(numar[i]&1==1)
		{
			printf("-1");
			return 0;
		}
	}
	euler(1);
	return 0;
}