Cod sursa(job #1259772)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 10 noiembrie 2014 16:14:02
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<cstdio>
#include<vector>

using namespace std;

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

const int nmax = 50000;
int first, last, nrp[ nmax + 1 ], q[ nmax ];

vector <int> v[ nmax + 1 ];

void solve( int x ) {
    for( int i = 0; i < (int)v[ x ].size(); ++ i ) {
        -- nrp[ v[ x ][ i ] ];
        if ( nrp[ v[ x ][ i ] ] == 0 ) {
            q[ last ++ ] = v[ x ][ i ];
        }
        solve( v[ x ][ i ] );
    }
}
int main() {
    int n, m, x, y;
    fscanf( fin, "%d%d", &n, &m );
    for( int i = 0; i < m; ++ i ) {
        fscanf( fin, "%d%d", &x, &y );
        v[ x ].push_back( y );
        ++ nrp[ y ];
    }
    first = last = 0;
    for( int i = 1; i <= n; ++ i ) {
        if ( nrp[ i ] == 0 ) {
            q[ last ++ ] = i;
        }
    }
    while ( first < last ) {
        x = q[ first ++ ];
        fprintf( fout, "%d ", x );
        solve( x );
    }
    fprintf( fout, "\n" );
    fclose( fin );
    fclose( fout );
    return 0;
}