Cod sursa(job #2615243)

Utilizator RazorBestPricop Razvan Marius RazorBest Data 13 mai 2020 21:59:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>

#define MAX_N 50000

int toposort(std::vector<int> adj[], int n, int *gr_ext) {
    int i;
    std::queue<int> q;
    int v[MAX_N + 1], len = 0;
    int node;

    for (i = 1; i <= n; i++) {
        if (gr_ext[i] == 0) {
            v[len++] = i;
            q.push(i);
        }
    }

    while (!q.empty()) {
        node = q.front();
        q.pop();

        for (auto it = adj[node].begin(); it != adj[node].end(); it++) {
            gr_ext[*it]--;
            if (gr_ext[*it] == 0) {
                v[len++] = *it;
                q.push(*it);
            }
        }
    }

    for (i = 1; i <= n; i++) {
        printf("%d ", v[len - i]);
    }
}

int main() {
    int i, j, n, m, x, y;
    std::vector<int> adj[MAX_N + 1];
    int gr_ext[MAX_N + 1] = {0};

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

    scanf("%d %d\n", &n, &m);
    while (m--) {
        scanf("%d %d", &x, &y);
        gr_ext[x]++;
        adj[y].push_back(x);
    }

    toposort(adj, n, gr_ext);

    return 0;
}