Cod sursa(job #1687197)

Utilizator DysKodeTurturica Razvan DysKode Data 12 aprilie 2016 18:36:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <set>
#include <queue>

using namespace std;

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

set < int > Graf[ 50010 ];
set < int > :: iterator it;
queue < int > Q;
int Deg[50010],i,j,n,m,x,y;

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        if( Graf[ x ].find( y ) == Graf[ x ].end() )
        {
            Deg[ y ]++;
            Graf[ x ].insert( y );
        }
    }

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

    while( Q.size() )
    {
        fout<<Q.front()<<' ';
        it = Graf[ Q.front() ].begin();
        for( ; it != Graf[ Q.front() ].end() ; it++ )
        {
            Deg[ *it ]--;
            if( Deg[ *it ] == 0 )
                Q.push( *it );
        }
        Q.pop();
    }

return 0;
}