Cod sursa(job #1647578)

Utilizator DysKodeTurturica Razvan DysKode Data 10 martie 2016 21:12:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <set>
#include <queue>

using namespace std;

multiset <int> G[50010];
queue <int> Q;
int n,m,i,j,deg[50010],x,y;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        deg[ y ]++;
        G[ x ].insert( y );
    }

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

    while( Q.size() )
    {
        fout<<Q.front()<<' ';
        x = Q.front();
        Q.pop();
        for( multiset<int>::iterator it = G[ x ].begin() ; it != G[ x ].end() ; it++ )
        {
            deg[ *it ]--;
            if( deg[ *it ] == 0 )
                Q.push( *it );
        }
    }

return 0;
}