Cod sursa(job #2786192)

Utilizator Albert_GAlbert G Albert_G Data 20 octombrie 2021 15:12:42
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <queue>
#include <vector>

std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");

const int N = 5e4+1;
std::vector<int> g[N];
int n, m, nrP[N];

void bfs(){
    std::queue<int> q;
    for(int i=1;i<=n;++i)
        if(!nrP[i]) q.push(i);
    while(!q.empty()){
        int currNode = q.front();
        q.pop();
        out<<currNode<<' ';
        for(auto node : g[currNode]){
            --nrP[node];
            if(!nrP[node])
                q.push(node);
        }
    }
}

int main(){
    in>>n>>m;
    for(int i=0;i<m;++i){
        int a,b;
        in>>a>>b;
        g[a].push_back(b);
        ++nrP[b];
    }
    bfs();
    in.close();
    out.close();
    return 0;
}