Cod sursa(job #613187)

Utilizator BitOneSAlexandru BitOne Data 17 septembrie 2011 20:58:37
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 50011

using namespace std;
int gradExt[N_MAX];
vector< int > stOrder;
vector< int > Gt[N_MAX];
vector< int >::const_iterator it, iend;
int main( void )
{
    unsigned int N, i;
    int M, x, y;
    ifstream in( "sortaret.in" );
    for( in>>N>>M; M; --M )
    {
        in>>x>>y;
        Gt[y].push_back( x );
        ++gradExt[x];
    }
    for( i=1; i <= N; ++i )
        if( !gradExt[i] )
            stOrder.push_back( i );
    for( i=0; N > stOrder.size(); ++i )
    {
        for( it=Gt[i].begin(), iend=Gt[i].end(); it < iend; ++it )
        {
            --gradExt[*it];
            if( 0 == gradExt[*it] )
            {
                stOrder.push_back( *it );
                if( N == stOrder.size() )
                    break;
            }
        }
    }
    ofstream out( "sortaret.out" );
    copy( stOrder.begin(), stOrder.end(), ostream_iterator<int>( out, " " ) );
    out<<'\n';
    return EXIT_SUCCESS;
}