Pagini recente » Cod sursa (job #2750215) | Cod sursa (job #2083947) | Cod sursa (job #909849) | Cod sursa (job #2784739) | Cod sursa (job #418709)
Cod sursa(job #418709)
#include<cstdio>
#include<iostream>
using namespace std;
struct nod
{
int info;
nod *next;
};
#define nn 100005
nod *g[nn];
int e[nn],n,m,grad[nn],v[nn];
void adauga(int a,int b)
{
nod *p=new nod;
p->info=b;
p->next=g[a];
g[a]=p;
}
void sterg(int k,int kk)
{
--grad[k];
--grad[kk];
int pp=1;
for(nod *p=g[k],*q=p->next;p&&q&&pp;)
if(q->info==kk)
{
p->next=q->next;
delete q;
q=p->next;
pp=0;
}
else
p=p->next,q=q->next;
if(g[k]->info==kk)
{
nod *p=g[k];
g[k]=g[k]->next;
delete p;
}
}
void euler(int k)
{
while(g[k])
{
int kk=g[k]->info;
sterg(k,kk);
euler(kk);
}
e[++m]=k;
}
void bfs()
{
int coada[nn],st,dr;
coada[1]=1;
st=dr=1;
v[1]=1;
while(st<=dr)
{
for(nod *p=g[coada[st]];p;p=p->next)
if(!v[p->info])
{
v[p->info]=1;
coada[++dr]=p->info;
}
++st;
}
}
int posibil()
{
bfs();
int pp=1;
for(int i=1;i<=n&&pp;++i)
if(!v[i]||grad[i]%2)
pp=0;
if(!pp)return 0;
return 1;
}
int main()
{
int a,b;
freopen("ciclueuler.in","r",stdin);
scanf("%d%d",&n,&m);
for(;m;--m)
{
scanf("%d%d",&a,&b);
adauga(a,b);
++grad[a];
}
if(posibil())
euler(1);
freopen("ciclueuler.out","w",stdout);
if(m)
for(int i=1;i<=m;++i)
printf("%d ",e[i]);
else
printf("-1");
return 0;
}