Cod sursa(job #503963)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 25 noiembrie 2010 22:11:23
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <stdlib.h>

struct point {
	int inf;
	point *leg;
};
point *a[100001];
int i,n,m,x,y,nc,ok;
int c[500001];
int ap[100001];


void insert(int x,int y) {
	point *p;
	p=new point;
	p->inf=y;
	p->leg=a[x];
	a[x]=p;
}

void cautare(int y,int x) {
	point *p,*u;
	int ok;
	u=NULL;
	p=a[y];
	ok=0;
	while (p!=NULL) {
		if (p->inf==x) {
			ok=1;
			break;
		}
		u=p;
		p=p->leg;
	}
	if (ok) {
		if (u!=NULL) {
			p=u->leg->leg;
			u->leg=p;
		}
		else a[y]=p->leg;
	}
}
	
void Df(int x) {
	int y;
	while (a[x]!=NULL) {
		y=a[x]->inf;
		a[x]=a[x]->leg;
		cautare(y,x);
		Df(y);
	}
	c[nc]=x;
	nc++;
}

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);
		insert(x,y);
		insert(y,x);
		ap[x]++;
		ap[y]++;
	}
	ok=1;
	for (i=1; i<=n; i++) 
		if (ap[i]%2==1) {
			ok=0;
			break;
		}
	if (ok){
	Df(1);
	for (i=0; i<nc-2; i++) printf("%d ",c[i]);
	printf("%d\n",c[nc-2]);
	}
	else printf("-1\n");
	return 0;
}