Cod sursa(job #3250819)

Utilizator tobiasSpartanu89Rosianu Radu tobiasSpartanu89 Data 23 octombrie 2024 19:15:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

const int NMAX = 1e5;
std::vector<int> L[NMAX + 1];
int deg[NMAX + 1];
int N, M;

void kahn(){
    std::queue<int> zeroDeg;

    for (int i = 1; i <= N; i++)
        if (deg[i] == 0) {
            zeroDeg.push(i);

        }

    while (!zeroDeg.empty()){
        auto node = zeroDeg.front();
        for (auto next: L[node]) {
            deg[next]--;
            if (deg[next] == 0) {
                zeroDeg.push(next);
            }
        }
        zeroDeg.pop();
        g << node << " ";
    }
}

int main() {

    f >> N >> M;
    for(int i = 1; i <= M; ++i){
        int x, y;
        f >> x >> y;
        L[x].push_back(y);
        deg[y]++;

    }
    kahn();
    return 0;
}