Cod sursa(job #313077)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 7 mai 2009 22:06:10
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
# include <stdio.h>
int s[200001],i,j,n,m,x,y,k,ok,sf,k2;
struct nod
{
int info;
nod *urm;
}*a[1000001],*p,*v,*z,*q,*w;

void df (int x)
{
nod *p;
s[x]=1;
p=a[x];
while (p)
{
if (s[p->info]==0)
df (p->info);
p=p->urm;
}
}



void ciclu ()
{
while (q)
{
k2=q->info;
p=a[k2];


if (p)
{
k=p->info;
v=new nod;
v->info=k;
v->urm=q->urm;
q->urm=v;


p=a[k2];
a[k2]=p->urm;


p=a[k];
if (p->info==k2)
{
p=p->urm;
a[k]=p;
}
else
while (p->urm)
{
if (p->urm->info==k2)
{
v=p->urm;
p->urm=v->urm;

}
p=p->urm;
}






}


q=q->urm;
}
}


int main ()
{
freopen ("ciclueuler.in","r",stdin);
freopen ("ciclueuler.out","w",stdout);
scanf ("%i%i",&n,&m);
for (i=1;i<=m;i++)
{
scanf ("%i%i",&x,&y);
p=new nod;
p->info=x;
p->urm=a[y];
a[y]=p;
p=new nod;
p->info=y;
p->urm=a[x];
a[x]=p;
}
for (i=1;i<=n;i++)
{
k=0;
p=a[i];
while (p)
{
k++;
p=p->urm;
}
if (k%2==1)
ok=1;
}
df (1);
for (i=1;i<=n;i++)
if (s[i]==0)
ok=1;
if (ok==1)
printf ("-1");
else
{
z=new nod;
z->info=1;
z->urm=0;
w=z;
while (z)
{
q=z;
ciclu ();
z=z->urm;
}
z=w;
while (z->urm)
{
printf ("%i ",z->info);
z=z->urm;
}
}
return 0;
}