Cod sursa(job #2253247)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 3 octombrie 2018 20:09:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define NMAX 50005

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

int main () {

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

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

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

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

    while ( !Q.empty() ) {
        nod = Q.front(); Q.pop();
        printf( "%d ", nod );
        for ( i = 0; i < V[ nod ].size(); ++i ) {
            Grad[ V[ nod ][ i ] ]--;
            if ( Grad[ V[ nod ][ i ] ] == 0 ) Q.push( V[ nod ][ i ] );
        }
    }

    return 0;
}