Cod sursa(job #2664035)

Utilizator dianapingu1Diana Vasiliu dianapingu1 Data 27 octombrie 2020 19:59:31
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>

using namespace std;

int main() {

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

    int n,m;

    fin >> n >> m;
    vector<int> gradin(n+1);
    vector<int> sortare;
    vector<int> muchii[n+1];

    for (int i = 0; i < n; i++) {
        int x,y;
        fin >> x >> y;
        muchii[x].push_back(y);
        gradin[y]++;
    }

    for (int i = 1; i <= n; i++) {
        if (gradin[i] == 0) {
            sortare.push_back(i);
        }
    }

    for (int i = 0; i < n; i++) {
        int nod = sortare[i];

        for (auto &vecin : muchii[nod]) {
            gradin[vecin]--;
            if (gradin[vecin] == 0) {
                sortare.push_back(vecin);
            }
        }
    }

    for (auto &nod : sortare) {
        fout << nod << " ";
    }

    fin.close();
    fout.close();
    return 0;
}