Cod sursa(job #2422963)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 20 mai 2019 14:59:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <vector>
#include <queue>

const int NMAX  = 50001;

int G[ NMAX ];
std :: vector < int > V[ NMAX ];

std :: vector < int > SortareTopologica( int n ) {

    int i, j, x;
    std :: queue < int > Q;
    std :: vector < int > Sol;

    for ( i = 1; i <= n; ++i ) {
        if ( G[ i ] == 0 ) {
            Q.push( i );
        }
    }

    while ( !Q.empty() ) {
        x = Q.front();
        Sol.push_back( x );
        Q.pop();

        for ( int i = 0; i < V[ x ].size(); ++i ) {
            G[ V[ x ][ i ] ]--;
            if ( G[ V[ x ][ i ] ] == 0 ) {
                Q.push( V[ x ][ i ] );
            }
        }

    }

    return Sol;

}

int main () {

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

    int n, m, i, j, x, y;
    std :: vector < int > Sortate;

    std :: cin >> n >> m;
    while ( m-- ) {
        std :: cin >> x >> y;
        V[ x ] .push_back( y );
        G[ y ]++;
    }

    Sortate = SortareTopologica( n );
    for ( int i = 0; i < Sortate.size(); ++i ) {
        std :: cout << Sortate[ i ] << " ";
    }

    return 0;
}