Cod sursa(job #1117644)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 23 februarie 2014 18:26:27
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>

#define N_MAX 50000
#define M_MAX 100000

int N, M, sp, anssp;
int list[ M_MAX + 1 ], next[ M_MAX + 1 ], beg[ N_MAX + 1 ], end[ N_MAX + 1 ];
int deg[ N_MAX + 1 ], ans[ N_MAX + 1 ];

void add( int s, int f ) {
    list[ ++ sp ] = f;
    if( beg[ s ] ) {
        next[ end[ s ] ] = sp;
        end[ s ] = sp;
    } else {
        beg[ s ] = end[ s ] = sp;
    }
}

void tsort( ) {
    int i, x;

    for( i = 1; i <= N; i ++ ) {
        if( deg[ i ] == 0 ) {
            ans[ ++ anssp ] = i;
        }
    }

    for( i = 1; i <= N; i ++ ) {
        x = ans[ i ];
        int curr = beg[ x ];
        while( curr ) {
            if( ( -- deg[ list[ curr ] ] ) == 0 ) {
                ans[ ++ anssp ] = list[ curr ];
            }
            curr = next[ curr ];
        }
    }
}

int main( ) {
    FILE * fin, * fout;
    fin = fopen( "sortaret.in", "r" );
    fout = fopen( "sortaret.out", "w" );

    fscanf( fin, "%d%d", &N, &M );

    int i;
    for( i = 1; i <= M; i ++ ) {
        int s, f;
        fscanf( fin, "%d%d", &s, &f );
        add( s, f );
    }

    tsort( );

    for( i = 1; i <= N; i ++ ) {
        fprintf( fout, "%d ", ans[ i ] );
    }

    fclose( fin );
    fclose( fout );
}