Cod sursa(job #2348380)

Utilizator gabrielmGabriel Majeri gabrielm Data 19 februarie 2019 17:42:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

using ListaVecini = vector<int>;
using Graf = vector<ListaVecini>;

int main() {
    ifstream in{ "sortaret.in" };
    int n, m;
    in >> n >> m;

    Graf graf(n + 1);
    Graf incidente(n + 1);


    for (int i = 1; i <= m; ++i) {
        int start, end;
        in >> start >> end;

        graf[start].push_back(end);
        incidente[end].push_back(start);
    }

    vector<int> initiale;
    for (int i = 1; i <= n; ++i) {
        if (incidente[i].empty()) {
            initiale.push_back(i);
        }
    }

    vector<int> sortate;
    sortate.reserve(n);

    while (!initiale.empty()) {
        int nod = initiale.back();
        initiale.pop_back();

        sortate.push_back(nod);

        for (int vecin : graf[nod]) {
            auto poz = find(incidente[vecin].begin(), incidente[vecin].end(), nod);
            incidente[vecin].erase(poz);

            if (incidente[vecin].empty()) {
                initiale.push_back(vecin);
            }
        }
    }

    ofstream out{ "sortaret.out" };
    for (int i = 0; i < sortate.size(); ++i) {
        out << sortate[i] << ' ';
    }
    out << '\n';
}