Cod sursa(job #2603459)

Utilizator matthriscuMatt . matthriscu Data 19 aprilie 2020 21:50:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m, i, x, y, incoming[50005] = {0};
    vector<int> G[50005];
    queue<int> q;
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        ++incoming[y];
    }

    for(i = 1; i <= n; ++i)
        if(incoming[i] == 0)
            q.push(i);

    while(!q.empty()) {
        int nod = q.front(), s = G[nod].size();
        q.pop();
        printf("%d ", nod);
        for(i = 0; i < s; ++i) {
            --incoming[G[nod][i]];
            if(!incoming[G[nod][i]])
                q.push(G[nod][i]);
        }
    }
}