Cod sursa(job #269090)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 2 martie 2009 13:28:43
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 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;
nod *C;
while (k)
{
C = M[st[k]];

while (C!=NULL)
{
if (VER[C->poz]) C = C->next;
                    else {
                         VER[C->poz] = 1;
                         st[++k] = C->vec;
                         break;
                         }
printf("%d ",st[k--]);
}
}
*/
//for(nod* cur = M[x];cur != NULL; cur = cur -> next)
nod *cur = M[x];
while (cur!=NULL)
{
if (!VER[cur -> poz])
{
VER[cur -> poz] = 1;
dfs(cur -> vec);
printf("%d ",x);
}
cur = cur->next;
}
}

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;
}