Cod sursa(job #1460313)

Utilizator perjulucianPerju Lucian Ionut perjulucian Data 12 iulie 2015 12:49:33
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.7 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct Stack{
    int val ;
    struct Stack * next ;
}Stack ;
typedef struct graf{
    Stack **a; // matricea de adiacenta
    int n,m ; //n noduri , m muchii /arce 
}Graf ;     
   

Stack * push(Stack * s,int val){
    

    Stack * nou = (Stack*)malloc(sizeof(Stack));
    nou->val = val ;
    nou->next = s;
    s = nou ;
    return s ;
}

int * vazut = NULL ;
// stiva se foloseşte în două funcţii
// sortare topologică pornind dintr-un nod v
void ts (Graf g, int v,Stack ** s) {

    vazut[v] = 1;
 
    Stack * cursor = g.a[v];
    while(cursor != NULL){
        if(!vazut[cursor->val])
            ts(g, cursor->val,s);
        cursor = cursor->next ;
    }    
    

    *s = push(*s, v);
}
void init(Graf * g,int n ){
    g->n = n ; 
    g->m = 0 ; 
    
    g->a=(Stack**)calloc((n+1),sizeof(Stack*));
    

}
void add(Graf * g , int x , int y){//ATENTIE adauga arcuri , nu muchii
    g->m ++ ; // marcam faptul ca a fost adaugat un arc
    g->a[x]=push(g->a[x],y);

}
void print_stack(Stack * s,FILE * out){
    Stack * cursor = s ;
    while(cursor != NULL){
        fprintf(out,"%d ",cursor->val );
        cursor = cursor->next ;
    }
}
int main(){
    FILE * in = fopen("sortaret.in" , "r") ;
    FILE * out = fopen("sortaret.out","w") ;

    int N , M ;
    fscanf(in , "%d %d",&N,&M);
    Graf g  ;
    Stack * s = NULL ;
    vazut = (int*)calloc((N+1),sizeof(int));
    init(&g,N);
    int i ;
    int x , y ;
    for( i = 1 ; i <= M ; i++){
        fscanf(in,"%d %d",&x,&y);
        add(&g,x,y);
    }
    for (i = 1; i <= N; i++)
        if (vazut[i] == 0)
            ts(g, i,&s);

    print_stack(s,out);    
    
    fclose(in);
    fclose(out);
    return 0 ;
}