Nu aveti permisiuni pentru a descarca fisierul grader_test2.in
Cod sursa(job #269040)
Utilizator | Nezbeda Harald free2infiltrate | Data | 2 martie 2009 11:31:40 |
---|---|---|---|
Problema | Ciclu Eulerian | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.98 kb |
#include <stdio.h>
#define nmax 100001
struct nod
{
int x;
nod *urm;
};
nod *A[nmax];
int grad[nmax],st[500001],k=0;
void del(int x,int y)
{
if (A[x]!=NULL)
{
if (A[x]->x==y) A[x] = A[x]->urm;
else
{
while (A[x]->urm->x!=y && A[x]->urm!=NULL) A[x]=A[x]->urm;
if (A[x]->urm==NULL) return;
else A[x]->urm=A[x]->urm->urm;
}
}
}
void add(int x,int y)
{
nod *urm;
urm = new nod;
urm->x= y;
urm->urm = A[x];
A[x] = urm;
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
int n,m,x,y,i;
scanf("%d%d\n",&n,&m);
while (m)
{
m--;
scanf("%d%d\n",&x,&y);
grad[x]++;
grad[y]++;
if (x==y) add(x,y);
else add(x,y),add(y,x);
}
for (i=1;i<=n;i++) if (grad[i]%2==1)
{
printf("-1");
return 0;
};
k=1;
st[k]=1;
while (k)
{
x = st[k];
if (A[x]!=NULL) {
st[++k] = A[x]->x;
if (A[x]->x!=x) del(A[x]->x,x);
A[x]=A[x]->urm;
}
else if (k>1) printf("%d ",st[k--]);
else k--;
}
return 0;
}