Cod sursa(job #433160)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 3 aprilie 2010 13:47:02
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<stdio.h>
FILE *f,*g;
int t[4][2000000],c[200000],fin[200000],x,y,z,v[2000000],nr,numar,n,m,i,viz[200000],grad[200000],ok,prov[1000000];
void ciclu(int k)
{ int p=c[k]; 
  while(p)
   { if(p==c[k]) c[k]=t[2][p]; else t[2][prov[p]]=t[2][p];
     if(p%2==0) x=p-1; else x=p+1;
     if(x==c[t[1][p]]) c[t[1][p]]=t[2][x]; else t[2][prov[x]]=t[2][x];
	 x=t[2][x];
	 if(c[t[1][p]]) ciclu(t[1][p]); else p=0;
   }
  numar++; v[numar]=k; 
}
int main()
{ f=fopen("ciclueuler.in","r"); g=fopen("ciclueuler.out","w");
  fscanf(f,"%d%d",&n,&m);
  for(i=1;i<=m;i++)
   { fscanf(f,"%d%d",&x,&y); 
     if(c[x]==0) { nr++; prov[nr]=fin[x]; c[x]=nr; fin[x]=nr; t[1][nr]=y; grad[x]++; }
	 else { nr++; prov[nr]=fin[x]; t[2][fin[x]]=nr; t[1][nr]=y; fin[x]=nr; grad[x]++;}
	 z=x; x=y; y=z;
	 if(c[x]==0) { nr++; prov[nr]=fin[x]; c[x]=nr; fin[x]=nr; t[1][nr]=y; grad[x]++;}
	 else { nr++; prov[nr]=fin[x]; t[2][fin[x]]=nr; t[1][nr]=y; fin[x]=nr; grad[x]++;}
   }
  ok=1;
  for(i=1;i<=n;i++) if(grad[i]%2) ok=0; 
  if(ok) ciclu(1);
  if(ok) for(i=1;i<=m;i++) fprintf(g,"%d ",v[i]); else fprintf(g,"%d",numar);
  fclose(g);
  return 0;
}