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