Cod sursa(job #2425638)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 24 mai 2019 22:35:52
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int NMAX  = 50001;

int Grad[ NMAX ];
vector < int > V[ NMAX ];

vector < int > SortareTopologica ( int n ) {

    vector < int > sol;
    queue < int > Q;

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

    while( !Q.empty() ) {
        int nod = Q.front();
        sol.push_back( nod );
        Q.pop();
        for ( int i = 0; i < V[ nod ].size(); ++i ) {
            Grad[ V[ nod ][ i ] ]--;
            if ( Grad[ V[ nod ][ i ] ] == 0 ) {
                Q.push( V[ nod ][ i ] );
            }
        }
    }

    return sol;

}

int main () {

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

    int n, m, i, j;
    int x, y;

    scanf( "%d%d", &n,&m );
    while ( m-- ) {
        scanf( "%d%d", &x,&y );
        V[ x ].push_back( y );
        Grad[ y ]++;
    }

    vector < int > Sortate = SortareTopologica( n );
    for ( int i = 0; i < n; ++i ) {
        printf( "%d ", Sortate[ i ] );
    }

    return 0;

}