Cod sursa(job #3165170)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 5 noiembrie 2023 16:24:35
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <set>

using namespace std;

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

const int NMAX = 100003;
set<int> g[NMAX];
int res[NMAX], grad_in[NMAX], k;
bool exista[NMAX][NMAX];

int main() {

    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        if (!exista[x][y]) {
            g[x].insert(y);
            grad_in[y]++;
            exista[x][y] = true;
        }
    }

    while (k < n) {
        for (int i = 1; i <= n; i++) {
            if (grad_in[i] == 0) {
                res[++k] = i;
                grad_in[i]--;

                for (auto vec : g[i]) {
                    grad_in[vec]--;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
        fout << res[i] << ' ';


    return 0;
}