Pagini recente » Cod sursa (job #2685942) | Cod sursa (job #380187) | Cod sursa (job #3266196) | Cod sursa (job #3246630) | Cod sursa (job #248807)
Cod sursa(job #248807)
#include<stdio.h>
#include<stdlib.h>
#define IN "ccc.in"
#define OUT "ciclueuler.out"
#define MAX 100
int *G[MAX],Q[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 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<=G[x][0];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 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;
}