Cod sursa(job #303521)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 9 aprilie 2009 22:09:52
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>

struct nod
{
     int inf,poz;
     nod *next;
}*sir[100010];
int viz[500001];
int Q[5000000],inc,sf,n,m,num=1;
int grad[500010];

void baga(int a,int b,int pozitie)
{
     nod *q=new nod;
     q->inf=b;
     q->poz=pozitie;
     q->next=sir[a];
     sir[a]=q;
}

void citire()
{
     int a,b;
     freopen ("ciclueuler.in","r",stdin);
     freopen ("ciclueuler.out","w",stdout);
     scanf ("%d %d",&n,&m);
     for (int i=0;i<m;i++)
     {
          scanf ("%d %d",&a,&b);
          baga(a,b,i);
          grad[a]++;
          grad[b]++;
          baga(b,a,i);
     }
}

void df()
{
     int aux;
     Q[1]=1;
     while (num)
     {
          aux=num;
          for (nod *q=sir[Q[num]];q;q=q->next)
          {
               if (viz[q->poz])
                    continue;
               viz[q->poz]=1;
               Q[++num]=q->inf;
               break;
          }
          if (aux==num)
               printf("%d ",Q[num--]);
     }
}

int main ()
{
     citire();
     for (int i=1;i<=n;i++)
          if (grad[i]%2==1)
          {
               printf("-1\n");
               return 0;
          }
     df();
     printf("\n");
     return 0;
}