Cod sursa(job #2271935)

Utilizator DordeDorde Matei Dorde Data 29 octombrie 2018 15:13:08
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
int const NM = 5e4 + 7;
vector <int> G [NM];
int d [NM];
ifstream f ("sortaret.in");
ofstream g ("sortaret.out");
int n , m;
inline void bfs (){
    queue <int> Q;
    for(int i = 1 ; i <= n ; ++ i)
        if (! d [i]){
            Q . push (i);
            g << i << ' ';
        }
    while (! Q . empty ()){
        int node = Q . front ();
        vector <int> :: iterator it;
        for(it = G [node] . begin () ; it != G [node] . end () ; ++ it){
            -- d [*it];
            if (! d [*it]){
                Q . push (*it);
                g << *it << ' ';
            }
        }
        Q . pop ();
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++ i){
        int a , b;
        f >> a >> b;
        G [a] . push_back (b);
        ++ d [b];
    }
    bfs ();
    return 0;
}