Cod sursa(job #1177196)

Utilizator hrazvanHarsan Razvan hrazvan Data 26 aprilie 2014 11:57:42
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#define N_MAX 50000
#define M_MAX 100000
typedef struct{
    int vf,next;
}adjmat;

adjmat  adj[ M_MAX + 1 ];
int ult[ N_MAX + 1 ];
char  vizitat[ N_MAX + 1 ];
int rez[ N_MAX ], dr = 0;

void dfs ( int x ){
    vizitat[ x ] = 1;
    int k = ult[ x ];
    while ( k > 0 ){
        dfs ( adj[ k ] . vf );
        k = adj[ k ] . next;
    }
    rez[ dr ] = x;
    dr++;
    return ;
}

int main()
{
    FILE *in = fopen ( "sortaret.in", "r" );
    int n, m;
    fscanf ( in, "%d%d", &n, &m );
    int i, x, y, k = 1;
    for ( i = 0; i < m; i++ ){
        fscanf ( in, "%d%d", &x, &y );
        adj[ k ] . vf = y;
        adj[ k ] . next = ult[ x ];
        ult[ x ] = k;
        k++;
    }
    fclose ( in );

    for ( i = 1; i <= n; i++ ){
        if ( !vizitat[ i ] )    dfs ( i );
    }

    FILE *out = fopen ( "sortaret.out", "w" );
    for ( i = n - 1; i >= 0; i-- ){
        fprintf ( out, "%d ", rez[ i ] );
    }
    fclose ( out );
    return 0;
}