Cod sursa(job #410916)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 4 martie 2010 17:26:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

#define MAX_N 50005
#define MAX_S 10005

char s[ MAX_S ];
int N, M;
int cnt_s, g[ MAX_N ];
queue <int> q;
vector <int> v[ MAX_N ];

void read( int &val ) {

    while( !isdigit( s[ cnt_s ] ) )
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }

    val = 0;
    while( isdigit( s[ cnt_s ] ) ) {

        val = val*10 + s[ cnt_s ] - '0';
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }
    }
}

int main() {

    freopen( "sortaret.in", "r", stdin );
    freopen( "sortaret.out", "w", stdout );

    int i, x, y, nod;
    vector <int> :: iterator it;

    cnt_s = MAX_S - 1;

    read( N );
    read( M );

    while( M-- ) {

        read( x );
        read( y );

        ++g[ y ];
        v[ x ].push_back( y );
    }

    for( i = 1; i <= N; ++i )
        if( g[ i ] == 0 )
            q.push( i );

    while( !q.empty() ) {

        nod = q.front();
        q.pop();

        printf( "%d ", nod );

        for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
            if( --g[ *it ] == 0 )
                q.push( *it );
    }

    return 0;
}