Cod sursa(job #248890)

Utilizator vlad2179Popescu Vlad Alexandru vlad2179 Data 27 ianuarie 2009 00:30:09
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 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;
}
int conex(){
	int p,u,x,i,nr;
	for(Q[1]=1,p=0,u=1,viz[1]=1,nr=1;p<=u;){
		x=Q[++p];
		for(i=1;i<=grad[x];i++)
			if(!viz[G[x][i]]){
			  Q[++u]=G[x][i];viz[G[x][i]]=1;nr++;if(nr==n)return 1;}
	}
	return 0;
}

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");
	else{printf("1 "); for(int i=1;i<lg;i++) printf("%d ",Drum[i]);}
}

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();
	if(conex())
	solve();
	else afis(0);

	return 0;

}