Cod sursa(job #3369421)

Utilizator aspaNadu Tudor aspa Data 20 octombrie 2026 11:07:25
Problema Sortare topologica Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector<int> A[50001];
unordered_map<int, unordered_set<int>> B;
vector<int> result;
stack<int> grad_intern_zero;

int main() {
    int N, M;
    fin >> N >> M;
    int x, y;

    for (int i = 0; i < M; i++) {
        fin >> x >> y;
        A[x].push_back(y);

        B[y].insert(x);
    }

    for(int i = 1; i <= N; i++)
        if (B.find(i) == B.end()) grad_intern_zero.push(i);
    
    int n;
    while (!grad_intern_zero.empty()) {
        n = grad_intern_zero.top();
        grad_intern_zero.pop();
        result.push_back(n);

        for (auto m : A[n]) {
            B[m].erase(n);
            if (B[m].empty()) {
                grad_intern_zero.push(m);
            }
        }
    }

    for (auto x : result) {
        fout << x << " ";
    }

    return 0;
}