Cod sursa(job #3271545)

Utilizator vladm98Munteanu Vlad vladm98 Data 26 ianuarie 2025 15:24:03
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> graph[100005]; // graph[i] = este un vector <int> care retine toti vecinii nodului i
int gradIntrare[100005]; // gradIntrare[i] = retine gradul de intrare al nodului i

int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y); // deoarece este graph orientat, pushez doar pe y in lista de vecini ai lui x
        gradIntrare[y]++; // crestem gradul de intrare al lui y
    }

    queue <int> q; // o coada care contine nodurile cu grad de intrare 0 la momentul actual
    vector <int> topoSort; // va contine nodurile in ordinea sortata

    for (int i = 1; i <= n; i++) {
        if (gradIntrare[i] == 0) {
            q.push(i); // mai intai populam coada cu toate gradele de intrare 0
        }
    }

    while (!q.empty()) {
        int node = q.front(); // cat timp coada este goala, o sa imi iau un nod din ea - despre care stim ca are
        // grad de intrare 0
        q.pop(); // il scoatem din coada pentru ca nu o sa mai avem nevoie de el odata ce l am procesat

        topoSort.push_back(node); // deoarece are grad de intrare 0, il pot insera in sortarea topologica

        for (auto neighbor : graph[node]) {
            // trebuie sa scad gradul de intrare al fiecarui vecin al lui node cu 1
            gradIntrare[neighbor]--;

            // daca vecinul a ajuns la grad de intrare 0, trebuie sa il inserez in coada pentru a fi procesat uterior
            if (gradIntrare[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // afisez sortarea topologica
    for (auto node : topoSort) {
        cout << node << " ";
    }
}