Cod sursa(job #269058)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 2 martie 2009 12:08:38
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<stdio.h>
#include<malloc.h>

const int maxn = 140000;
const int maxmu = 500100;

struct nod
{
int vec;
int poz;
nod* next;
};


nod* M[maxn];
int N,MU;
int VER[maxmu],st[maxmu],k=0;
int GR[maxn];

void introduce(int vecin,int pozitie,int cur)
{
nod* nou = new nod;
nou -> vec = vecin;
nou -> poz = pozitie;
nou ->next = M[cur];
M[cur] = nou;
}

void dfs(int x)
{
st[++k]=x;
while (k)
{
if (M[st[k]]!=NULL)
        if (VER[M[st[k]]->poz]) M[st[k]] = M[st[k]]->next;
                    else {
                         VER[M[st[k]]->poz] = 1;
                         st[++k] = M[st[k]]->vec;
                         }
else printf("%d ",st[k--]);
}

/*
for(nod* cur = M[x];cur != NULL; cur = cur -> next)
{
if (VER[cur -> poz]) continue;
VER[cur -> poz] = 1;
dfs(cur -> vec);
printf("%d ",x);
}
*/
}

int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d %d\n",&N,&MU);
int i;
for(i = 1;i <= MU; ++i)
{
int x = 0,y = 0;
scanf("%d %d\n",&x,&y);
introduce(y,i,x);
introduce(x,i,y);
GR[x]++;GR[y]++;
}
for(i = 1;i <= N; ++i)
if (GR[i] % 2 == 1) {printf("-1\n");return 0;}
dfs(1);
return 0;
}