Cod sursa(job #754977)

Utilizator zseeZabolai Zsolt zsee Data 4 iunie 2012 12:36:34
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.59 kb
#include <stdio.h>
#include <stdlib.h>

struct LI {
	int t;
	struct LI *urm; // urmatorul element
};

struct LI *v, l;
int *ins;
FILE* fo;

void LI_ai( struct LI *c, int element ) {
       struct LI *b;
       b = (struct LI*) malloc( sizeof(struct LI) );
       b->t = element;
       b->urm = c;
       c = b;
}

void LI_ad( struct LI *d, int element ) {
       struct LI *b;
       b = (struct LI*) malloc( sizeof(struct LI) );
       b->t = element;
       b->urm = d->urm;
       d->urm = b;
}

void berak_rek( struct LI *d, int idx ) {
     if ( ins[idx] )
        return;
     ins[idx] = 1;
     LI_ad( d, idx );
     
     struct LI *p;
     p = v[idx].urm;
     
     while (p != NULL) {
           berak_rek( d->urm, p->t );
           p = p->urm;
     }
}

int main(void) {
  int n,m,i,x,y;
  
  FILE * f;
  f = fopen("sortaret.in", "r");
  fscanf(f,"%d %d", &n, &m);
  v = (struct LI *) malloc( (n+1)*sizeof( struct LI ) );
  ins = (int*) calloc( (n+1), sizeof( int ) );
  
  l.urm = NULL;
  for ( i = 0; i<=n; i++ ) {
      v[i].urm = NULL;
  }
      
  for ( i = 0; i<m; i++) {
      fscanf(f,"%d %d", &x, &y);
      LI_ad( &v[y], x );
  }
  
  for (i = 1; i<=n; i++ )
      berak_rek( &l, i );
  
  fo = fopen("sortaret.out", "w"); 
  x=1;
  for (i=1; i<=n; i++) {
      if (ins[i] == 0)
         ins[x++] = i;
  }
  
  i = n;
  struct LI* p;
  p = l.urm;
  while (p!=NULL) {
        ins[i--] = p->t;
        p = p->urm;
  }
  
  for (i=1;i<=n;i++)
      fprintf(fo,"%d ",ins[i]);
      
  
  fclose(fo);
  
  return 0;
}