Cod sursa(job #1959217)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 9 aprilie 2017 11:08:37
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ofstream fout ("sortaret.out");
ifstream fin ("sortaret.in");
int n,m,i,a,b;
queue < int > q;
vector < int > v[50005];
int rsp[50005],grad[50005];
int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>a>>b;
        grad[ b ]++;
        v[ a ].push_back( b );
    }
    for( i = 1 ; i <= n ; i++ )
        if( !grad[ i ] )
            q.push( i );
    for( i = 1 ; i <= n ; i++ )
    {
        rsp[ i ] = q.front();
        for( auto it : v[ q.front() ] )
        {
            grad[ it ]--;
            if( !grad[ it ] )
                q.push( it );
            fout<<it<<" ";
        }
        q.pop();
    }
    for( i = 1 ; i <= n ; i++ )
        fout<<rsp[ i ]<<" ";
}