Cod sursa(job #248898)

Utilizator vlad2179Popescu Vlad Alexandru vlad2179 Data 27 ianuarie 2009 00:55:41
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
#include<stdlib.h>
#define IN "ciclueuler.in"
#define OUT "ciclueuler.out"
struct muchie{int x,y;};
int *G[100010],Q[100010];
int St[100010],Drum[100010];
int n,m,niv,lg,viz[100010];
muchie M[500010];int grad[100010];

int eulerian(){
	for(int i=1;i<=n;i++)if(grad[i]&1)return 0;
	return 1;
}

void date(){
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d",&M[i].x,&M[i].y);
		grad[M[i].x]++;
		grad[M[i].y]++;
	}
	for(i=1;i<=n;i++){G[i]=(int*)malloc(grad[i]*sizeof(int));grad[i]=0;}
	for(i=1;i<=m;i++){
		int a=M[i].x;
		int b=M[i].y;
		G[a][++grad[a]]=b;
		G[b][++grad[b]]=a;
	}
}

void sterge(int a,int b){int i;
 for(i=1;i<=grad[a] && G[a][i]!=b;i++);
 int aux;aux=G[a][grad[a]];G[a][grad[a]]=G[a][i];G[a][i]=aux;
 grad[a]--;
 for(i=1;i<=grad[b] && G[b][i]!=a;i++);
  aux;aux=G[b][grad[b]];G[b][grad[b]]=G[b][i];G[b][i]=aux;
 grad[b]--;
}

void parcurg(int x){
 int y;
 while(1){
	if(!grad[x])break;
	y=G[x][grad[x]];
	sterge(x,y);
	St[++niv]=x;
	x=y;
 }
}

void afis(int how){
	if(!how)printf("-1\n");
	else{printf("1 "); for(int i=1;i<lg;i++) printf("%d ",Drum[i]);
	printf("\n");}
}

void solve(){
 if(!eulerian()) {afis(0);return;}
 int nod=1;
 parcurg(nod);
 while(niv){
  Drum[++lg]=St[niv];
  parcurg(St[--niv]);
 }afis(1);
}

int main(){
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	date();
	solve();

	return 0;

}