Cod sursa(job #3270727)

Utilizator radiantstorkAmadeus L radiantstork Data 24 ianuarie 2025 11:49:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

void citire(std::vector<std::vector<int>>& graf, std::vector<int>& grad, int& n) {
    int m;
    int i, j;
    std::ifstream f("sortaret.in");
    f>>n>>m;
    graf.resize(n);
    grad.resize(n, 0);
    while (m--) {
        f>>i>>j;
        graf[i - 1].push_back(j - 1);
        ++grad[j - 1];
    }
    f.close();
}

void sortareTopologica() {
    std::vector<std::vector<int>> graf;
    std::vector<int> grad;
    int n;
    citire(graf, grad, n);

    std::queue<int> q;
    for (int i = 0; i < n; ++i)
        if (!grad[i])
            q.push(i);

    std::ofstream g("sortaret.out");
    while (!q.empty()) {
        const int i = q.front();
        q.pop();
        g<<i + 1<<" ";
        for (const auto& j : graf[i])
            if (!--grad[j])
                q.push(j);
    }
    g.close();
}

int main() {
    sortareTopologica();
    return 0;
}