Cod sursa(job #295583)

Utilizator otilia_sOtilia Stretcu otilia_s Data 3 aprilie 2009 14:10:07
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 100005
int n,*L[NMAX],S[NMAX],ns,nl,C[NMAX],Q[NMAX];
bool viz[NMAX];

void citire()
{
 FILE *fin=fopen("ciclueuler.in","r");
 int m,i;
 fscanf(fin,"%d %d",&n,&m);
 for (i=1;i<=n;++i)
  { L[i]=(int*)realloc(L[i],sizeof(int)); L[i][0]=0;}
 while (m--)
  { int x,y;
   fscanf(fin,"%d %d",&x,&y);
   ++L[x][0];
   L[x]=(int*)realloc(L[x],(L[x][0]+1)*sizeof(int));
   L[x][L[x][0]]=y;
   ++L[y][0];
   L[y]=(int*)realloc(L[y],(L[y][0]+1)*sizeof(int));
   L[y][L[y][0]]=x;
  }
 fclose(fin);
}

int eulerian()
{
 int i;
 for (i=1;i<=n;++i)
  if (L[i][0]%2) return 0; 
 return 1;
}

void sterge(int v, int w)
{
 int poz=0,i;
 for (i=1;i<=L[v][0]&&!poz;++i)
  if (L[v][i]==w) poz=i;
 for (i=poz;i<L[v][0];++i)
  L[v][i]=L[v][i+1];
 L[v][0]--;
 poz=0;
 for (i=1;i<=L[w][0]&&!poz;++i)
  if (L[w][i]==v) poz=i;
 for (i=poz;i<L[w][0];++i)
  L[w][i]=L[w][i+1];
 L[w][0]--;
}

void euler(int v)
{
 while (L[v][0])
  {
   int w=L[v][1];
   S[++ns]=v;
   sterge(v,w);
   v=w;
  }
}

int ver()
{
 int v=eulerian();
 if (!v) return 0;
 ns=nl=0;

 do
  {
   euler(v);
   v=S[ns--];
   C[++nl]=v;
  }
 while (ns);
 return 1;
}

void afisare(int sol)
{
 FILE *fout=fopen("ciclueuler.out","w");
 if (!sol) fprintf(fout,"-1\n");
    else { int i;
	  for (i=nl;i;--i)
	   fprintf(fout,"%d ",C[i]);
	 }
 fclose(fout);
}

int main()
{
 citire();
 afisare(ver());
 return 0;
}