Cod sursa(job #1334831)

Utilizator lucian666Vasilut Lucian lucian666 Data 4 februarie 2015 18:28:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb


#include <fstream>
#include <queue>
#include <vector>


#define dim 50001
#define pb push_back

using namespace std;
ofstream out("sortaret.out");

int n , di[dim] ,m;

vector < int > G[dim] , sol;
typedef vector < int >:: iterator IT;

void read();
void topo();
void wrs();

int main()
{

    read();
    topo();
    wrs();

}

void read()
{

    ifstream in("sortaret.in");
    in >> n >> m;

    for( int x , y ; m ; --m )
    {
        in >> x >> y;
        G[x].pb(y);
        ++di[y];

    }

}

void topo()
{

    queue < int > Q;
    for( int i = 1 ; i<=n ; i++)
        if( !di[i] )
            Q.push(i);

    while(!Q.empty())
    {
        int k = Q.front();
            sol.pb(k);
        Q.pop();
        for( IT i = G[k].begin(); i!=G[k].end() ;++i)
        {
            --di[*i];
            if( di[*i] == 0 )
                Q.push(*i);
        }
    }

}

void wrs()
{

    for( IT i = sol.begin() ; i!=sol.end() ; ++i)
        out << *i << " ";

}