Cod sursa(job #3187543)

Utilizator AlessiaFrunzaAlessia Frunza AlessiaFrunza Data 29 decembrie 2023 13:55:14
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <queue>

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

int main() { 
    int numar_noduri, numar_arce;
    fin >> numar_noduri >> numar_arce;

    vector<int> grad_intern(numar_noduri, 0);
    vector<vector<int>> adiacenta(numar_noduri);

    for (int i = 0; i < numar_arce; i++) {
        int x, y;
        fin >> x >> y;
        x--; y--; 
        adiacenta[x].push_back(y);
        grad_intern[y]++;
    }

    queue<int> coada;

    for (int i = 0; i < numar_noduri; i++) {
        if (grad_intern[i] == 0) {
            coada.push(i);
        }
    }

    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        fout << (nod + 1) << " ";
        for (int vecin : adiacenta[nod]) {
            grad_intern[vecin]--;
            if (grad_intern[vecin] == 0) {
                coada.push(vecin);
            }
        }
    }

    return 0;
}