Pagini recente » Cod sursa (job #532866) | Cod sursa (job #943066) | Cod sursa (job #1900561) | Cod sursa (job #531750) | Cod sursa (job #280169)
Cod sursa(job #280169)
#include <stdio.h>
const long NMAX=100010;
const long MMAX=500010;
long *a[NMAX], x[MMAX], y[MMAX], d[NMAX], q[NMAX], n, m, vf, st[MMAX];
bool viz[NMAX];
void euler(long v);
void bf(long nod);
int main()
{
long i;
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
scanf("%ld%ld", &n, &m);
for (i=0; i<m; i++)
{
scanf("%ld%ld", &x[i], &y[i]);
d[x[i]]++;
d[y[i]]++;
}//for i
i=1;
while (i<=n)
{
if (d[i]%2)
{
printf("-1");
return 0;
}//if
i++;
}//while
for (i=1; i<=n; i++)
{
a[i]=new long[d[i]];
a[i][0]=0;
}//for i
for (i=0; i<m; i++)
{
a[x[i]][++a[x[i]][0]]=y[i];
a[y[i]][++a[y[i]][0]]=x[i];
}//for i
bf(1);
i=1;
while (i<=n)
{
if (!viz[i])
{
printf("-1");
return 0;
}//if
i++;
}//while
euler(1);
return 0;
}//main
void euler(long v)
{
long i, w;
st[vf++]=v;
while (vf>0)
{
v=st[vf-1];
i=1;
while ((!a[v][i])&&(i<a[v][0]))
i++;
if (a[v][i])
{
w=a[v][i];
d[v]--;
a[v][i]=0;
i=1;
while ((a[w][i]!=v)&&(i<a[w][0]))
i++;
if (a[w][i]==v)
{
a[w][i]=0;
d[w]--;
}//if
st[vf++]=w;
}//if
else
{
if (vf>1)
printf("%ld ", st[vf-1]);
vf--;
}//else
}//while
}//euler
void bf(long nod)
{
long u=0, p=0, i;
q[u++]=nod;
viz[nod]=1;
while (u!=p)
{
nod=q[p++];
for (i=1; i<=a[nod][0]; i++)
if (!viz[a[nod][i]])
{
q[u++]=a[nod][i];
viz[a[nod][i]]=1;
}//if
}//while
}//bf