Cod sursa(job #1460279)

Utilizator perjulucianPerju Lucian Ionut perjulucian Data 12 iulie 2015 11:14:36
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 2.15 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct Graf{
    int n,m; // noduri muchii
    int **matrix; // graf efectiv
}Graf ;
typedef struct Queue{
    int val ;
    struct Queue * next ;
}Queue ;

void init(Graf * g , int n){
    
    g->n = n ;
    g->matrix = (int**)malloc((n+1)*sizeof(int*));
    int i ;
    for (i = 0 ; i <= n ; i++)
        g->matrix[i] = (int*)calloc((n+1),sizeof(int));
    g->m = 0 ;

}
void add(Graf * g , int x , int y ){ // add doar pentru grafuri orientate
    g->matrix[x][y] = 1 ;
    g->m ++ ;
}
void print_graf(Graf g){
    int i , j ; 
    for (i = 1 ; i <= g.n;i++){
        printf("\n");
        for(j = 1 ; j <= g.n ;j++)
            printf("%d ",g.matrix[i][j] );
    }
}
int grad_intern(Graf g ,int nod ){
    int i ;
    
    for ( i = 1 ; i <= g.n; i++)
        if(g.matrix[nod][i] != 0 )
            return 0 ;
    return 1 ;    
}
void add_queue(Queue ** front , Queue ** rear , int val){
    if(*front == NULL){
        *front = (Queue *)malloc(sizeof(Queue));
        (*front)->val = val ;
        (*front)->next = NULL ;
        *rear = *front ;
        return ;
    }
    Queue * nou = (Queue*)malloc(sizeof(Queue));
    nou->val = val ;
    nou->next = NULL ;
    (*rear)->next = nou ;
    *rear = nou ;

}

void ts(Graf g , int nod, int * vizitat,FILE * out){
    vizitat[nod] = 1 ;
    fprintf(out,"%d ",nod );
    int i ;
    for (i = g.n; i >= 0 ; i--)
        if(g.matrix[i][nod] && !vizitat[i])
            ts(g,i,vizitat,out);

}
int main(){
    FILE * in = fopen("sortaret.in" , "r") ;
    FILE * out = fopen("sortaret.out","w") ;
    int N , M ;
    Queue * front = NULL;
    Queue * rear = NULL ; 
    fscanf(in,"%d %d",&N,&M);
    Graf g  ;
    int * vizitat = (int*)calloc(N,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(grad_intern(g,i))
            add_queue(&front,&rear,i);  
    Queue * cursor = front ;
    while(cursor != NULL){
        ts(g,cursor->val,vizitat,out);
        cursor = cursor->next ;
    }   
    fprintf(out,"\n" );
    fclose(in);
    fclose(out);
    return 0 ;
}