Cod sursa(job #1330515)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 30 ianuarie 2015 19:04:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define IN_FILE "sortaret.in"
#define OUT_FILE "sortaret.out"
#define MAX_N 50000

FILE *f;

int pred[ MAX_N + 1 ];
queue < int > Q;
vector < int > sol;
vector < int > succ[ MAX_N + 1 ];
int N, M;

void citire( ) {
    int a, b;

    f = fopen( IN_FILE, "r" );
    fscanf( f, "%d%d", &N, &M );
    for( register int i = 0; i < M; ++i ) {
        fscanf( f, "%d%d", &a, &b );
        ++pred[ b ];
        succ[ a ].push_back( b );
    }
    fclose( f );
}
void rezolva( ) {
    int a;
    for( register int i = 1; i <= N; ++i ) {
        if( !pred[ i ] )
            Q.push( i );
    }
    while( !Q.empty( ) ) {
        a = Q.front( );
        Q.pop( );
        sol.push_back( a );
        for( vector < int > :: iterator it = succ[ a ].begin( );  it != succ[ a ].end( ); ++it ) {
            --pred[ *it ];
            if( !pred[ *it ] )
                Q.push( *it );
        }
    }
}
void afisare( ) {
    f = fopen( OUT_FILE, "w" );
    for( vector< int > :: iterator it = sol.begin( ); it != sol.end( ); ++it )
        fprintf( f, "%d ", *it );
    fputc( '\n', f );
    fclose( f );
}
int main( ) {
    citire( );
    rezolva( );
    afisare( );
}