Cod sursa(job #248725)

Utilizator vlad2179Popescu Vlad Alexandru vlad2179 Data 26 ianuarie 2009 18:28:51
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define IN "ciclueuler.in"
#define OUT "ciclueuler.out"
#define MAX 100001
int *G[MAX];
int St[MAX],Drum[MAX];
int n,m,niv,lg,viz[MAX];

int eulerian(){
	for(int i=1;i<=n;i++)if(G[i][0]%2)return 0;
	return 1;
}
int conex(){
	int Q[MAX],p,u,x,i,nr;
        memset(Q,0,sizeof(Q));
	for(Q[1]=1,p=0,u=1,viz[1]=1,nr=1;p<=u;){
		x=Q[++p];
		for(i=1;i<=G[x][0];i++)
			if(!viz[G[x][i]]){
				Q[++u]=G[x][i];viz[G[x][i]]=1;nr++;}
	}
	return (nr==n);
}

void date(){
	int x,y,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){G[i]=(int*)realloc(G[i],sizeof(int));G[i][0]=0;}
	for(;m--;){
		scanf("%d%d",&x,&y);
		G[x][0]++;
		G[x]=(int*)realloc(G[x],(G[x][0]+1)*sizeof(int));
		G[x][G[x][0]]=y;
		G[y][0]++;
		G[y]=(int*)realloc(G[y],(G[y][0]+1)*sizeof(int));
		G[y][G[y][0]]=x;
	}
}

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

void parcurg(int x){
 int y;
 while(1){
	if(!G[x][0])break;
	y=G[x][G[x][0]];
	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;

}