Cod sursa(job #754975)

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

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

struct LI *v, l;
char *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;
     }
}

void p_l( struct LI *c ) {
     while ( c!=NULL ) {
           printf("%d ",c->t);
           c = c->urm;
     }
     printf("\n");
}

void p_l_i_r( struct LI *c ) {
     if ( c == NULL )
        return;
     p_l_i_r( c->urm );
     fprintf(fo, "%d ", c->t );
}

void p_l_i( struct LI *c ){
     p_l_i_r( c );
     printf("\n");
}

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 = (char*) calloc( (n+1), sizeof( char ) );
  
  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"); 
    
  p_l_i( l.urm );
  
  fclose(fo);
  
  return 0;
}