Cod sursa(job #1725367)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 5 iulie 2016 15:59:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define NMAX 50005
#define INFI 0x3f3f3f

queue < int > Q;
vector < int > v[ NMAX ];

int sol[ NMAX ];
int grad[ NMAX ];
int vizt[ NMAX ];

void sortare( int n ){

    int i, j, k;
    j = 0;

    for( i = 1; i <= n; ++i )
        if( !grad[ i ] ) Q.push( i );

    while( !Q.empty() ){
        k = Q.front();
        sol[ ++j ] = k;
        for( i = 0; i < v[ k ].size(); ++i ){
            --grad[ v[ k ][ i ] ];
            if( !grad[ v[ k ][ i ] ] ) Q.push( v[ k ][ i ] );
        }
        Q.pop();
    }

}

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

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

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

    sortare( n );
    for( i = 1; i <= n; ++i ) printf("%d ",sol[ i ]);

    return 0;

}