Cod sursa(job #2425441)

Utilizator vlad00Vlad Stoleru vlad00 Data 24 mai 2019 20:22:09
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <list>
#include <vector>
#include <queue>

int main() {
    int N, M;
    std::ifstream f("sortaret.in");
    std::ofstream g("sortaret.out");
    f >> N >> M;
    std::list<int> *adj = new std::list<int>[N];
    std::vector<int> grade(N);
    for(int i = 0; i < M; ++i) {
        int X, Y;
        f >> X >> Y;
        adj[X].push_back(Y);
        grade[Y]++;
    }
    std::queue<int> result;
    for(size_t i = 0; i < grade.size(); ++i)
        if(grade[i] == 0)
            result.push(i);
    while(!result.empty()) {
        int st = result.front();
        g << st + 1 << ' ';
        result.pop();
        for(int nod : adj[st]) {
            grade[nod]--;
            if(!grade[nod])
                result.push(nod);
        }
    }
    return 0;
}