Cod sursa(job #2364868)

Utilizator AplayLazar Laurentiu Aplay Data 4 martie 2019 11:11:33
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define N_MAX 50001

int N, M, inDegree[N_MAX];
vector<int> graph[N_MAX];
queue<int> ready;

int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d%d", &N, &M);
    for (int it = 0; it < M; ++it) {
        int s, d;
        scanf("%d%d", &s, &d);
        graph[--s].push_back(--d);
        ++inDegree[d];
    }

    for (int it = 0; it < N; ++it)
        if (0 == inDegree[it]) ready.push(it);
    
    while (!ready.empty()) {
        int current = ready.front();
        ready.pop();
        printf("%d ", 1 + current);
        inDegree[current] = -1;
        for (int it = 0; it < graph[current].size(); ++it) {
            --inDegree[graph[current][it]];
            if (0 == inDegree[graph[current][it]]) {
                ready.push(graph[current][it]);
            }
        }
    }

    return 0;
}