Pagini recente » Cod sursa (job #2274997) | Cod sursa (job #2600721) | Cod sursa (job #2827271) | Cod sursa (job #1603626) | Cod sursa (job #586486)
Cod sursa(job #586486)
#include <stdio.h>
int n,m,gr[100001],i,ok,luat[100001],sol[100004],x,y;
struct nod{int y; nod *next;};
nod *G[100001];
void add(int x,int y)
{
nod *nou=new nod;
nou->y=y;
nou->next=G[x];
G[x]=nou;
}
int dfs(int x)
{
nod *nou=new nod;
nou=G[x];
while (nou)
{
if (!luat[nou->y])
{
luat[nou->y]=1;
dfs(nou->y);
}
nou=nou->next;
}
return 0;
}
int caut(int v)
{
while (1)
{
nod *nou=new nod;
if (G[v]==NULL) break;
int w=G[v]->y;
G[v]=G[v]->next;
if (G[w]->y==v)
G[w]=G[w]->next;
else
{
nou=G[w];
while (nou->next->y!=v && nou->next)
nou=nou->next;
if (nou->next->next)
nou->next=nou->next->next;
else nou->next=NULL;
}
sol[++sol[0]]=v;
v=w;
}
return 0;
}
int main(void)
{
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);
gr[x]++;
gr[y]++;
}
ok=1;
for (i=1;i<=n && ok;i++)
if (gr[i]%2) ok=0;
if (ok)
{
luat[1]=1;
dfs(1);
for (i=1;i<=n && ok;i++)
if (!luat[i])
ok=0;
}
if (!ok)
{
printf("-1\n");
return 0;
}
caut(1);
for (i=1;i<=sol[0];i++)
printf("%d ",sol[i]);
printf("\n");
return 0;
}