Cod sursa(job #3270733)

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

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

void dfs(std::vector<std::vector<int> > &graf, std::vector<bool> &viz, std::stack<int> &s, std::vector<bool> &inStiva,
         const int u) {
    viz[u] = true;
    for (const auto &v: graf[u])
        if (!viz[v])
            dfs(graf, viz, s, inStiva, v);
    s.push(u + 1);
    inStiva[u] = true;
}

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

    std::vector viz(n, false);
    std::vector inStiva(n, false);
    std::stack<int> s;
    for (int i = 0; i < n; ++i)
        if (!viz[i])
            dfs(graf, viz, s, inStiva, i);

    std::ofstream g("sortaret.out");
    while (!s.empty()) {
        const int u = s.top();
        s.pop();
        g << u << " ";
    }
}

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