Cod sursa(job #256741)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 12 februarie 2009 06:43:00
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<stdio.h>

#define MAX 100001
#define MAX2 500001
#define IN "ciclueuler.in"
#define OUT "ciclueuler.out"

FILE *f=fopen(IN,"r");
FILE *g=fopen(OUT,"w");

int n,m,grad[MAX];

struct nod
{
 int info;
 nod *urm;
}*prim[MAX];

void insert(int,int);
void elim(int,int);
void euler();
int check();
void read();

int main()
{
 read();
  fclose(f);

 if(check()==0)
  fprintf(g,"-1\n");
 else
  euler();

 fclose(g);

return 0;
}

void insert(int x, int y)
{
 nod *p,*q;

 grad[x]++;
 grad[y]++;

 p=new nod;
 p->info=y;
 p->urm=prim[x];
 prim[x]=p;

 q=new nod;
 q->info=x;
 q->urm=prim[y];
 prim[y]=q;
}

void elim(int x, int y)
{
 //elimin muchia x,y
 // sterg prim[x]

 nod *q;

 q=prim[x];
 prim[x]=prim[x]->urm;
 delete(q);

 nod *p,*r;
 if(prim[y]->info==x)
 {
  p=prim[y];
  prim[y]=prim[y]->urm;
  delete(p);
 }
 else
  for(r=prim[y]; r->urm; r=r->urm)
   if(r->urm->info == x)
   {
    p=r->urm;
    r->urm = r->urm->urm;
    delete(p);
    break;
   }
}

void euler()
{
 int x,vf,k=0;
 int st[MAX2],sol[MAX2];

 vf=0;
 st[++vf]=1;

 while(vf)
 {
  x=st[vf];

  if(prim[x]!=NULL)
  {
   st[++vf]=prim[x]->info;
   elim(x,prim[x]->info);
  }
  else
   sol[++k]=st[vf--];
 }

 for(int i=1;i<k;++i)
  fprintf(g,"%d ",sol[i]);
}

int check()
{
 int i;

 for(i=1;i<=n;++i)
  if(grad[i]%2==1)
   return 0;
return 1;
}

void read()
{
 int x,y;

 fscanf(f,"%d %d",&n,&m);

 while(m--)
 {
  fscanf(f,"%d %d",&x,&y);
  insert(x,y);
 }
}