Cod sursa(job #504345)
#include <stdio.h>
int pos,i,x,y,n,m,gr[100001],stack[500001];
struct tree
{
int nod;
tree *link;
}*T[100001];
void addnod(int x,int y)
{
tree *p;
p=new tree;
p->nod=x;
p->link=T[y];
T[y]=p;
}
void delnod(int x,int y)
{
tree *p,*q,*r;
p=T[x];
q=NULL;
while(p!=NULL)
{
if(p->nod==y)
if(q==NULL)
{
r=p;
T[x]=p->link;
delete r;
break;
}
else
{
r=p;
q->link=p->link;
delete r;
break;
}
q=p;
p=p->link;
}
}
void euler(int nod)
{
tree *p,*q;
int x;
p=T[nod];
while(p!=NULL)
{
q=p;
x=p->nod;
T[nod]=p->link;
delnod(x,nod);
delete q;
euler(x);
p=T[nod];
}
stack[++pos]=nod;
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) gr[i]=0;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
addnod(x,y);
addnod(y,x);
gr[x]++;
gr[y]++;
}
for(i=1;i<=n;i++)
if(gr[i]%2!=0)
{
printf("-1\n");
return 0;
}
pos=0;
euler(1);
for(i=pos;i>2;i--)
printf("%d ",stack[i]);
printf("%d\n",stack[2]);
return 0;
}