InfoGIM 17.04.2021 Sortare topologica

#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100005
using namespace std;
ifstream fin("topsort.in");
ofstream fout("topsort.out");

int n, m;
int x, y;
int gi[NMAX];
vector<int> G[NMAX];
queue<int> Q;

int main()
{
    fin >> n >> m;
    for (int i=1;i<=m;++i) {
        fin >> x >> y;
        G[x].push_back(y);
        ++gi[y];
    }
    for (int i=1;i<=n;++i) {
        if (gi[i] == 0) {
            Q.push(i);
        }
    }
    while (!Q.empty()) {
        int nodCurent = Q.front();
        Q.pop();
        // Stim sigur ca nodul "nodCurent" are gradul interior 0
        fout << nodCurent << ' ';
        int sz = G[nodCurent].size();
        for (int i=0;i<sz;++i) {
            int vecin = G[nodCurent][i];
            --gi[vecin];
            if (gi[vecin] == 0) {
                // Toate nodurile care aveau arce ce intrau in acest nod au fost puse
                // In sortarea topologica, nodul "vecin" poate fi adaugat si el
                Q.push(vecin);
            }
        }
    }
    fin.close();
    fout.close();
    return 0;
}