Cod sursa(job #2668117)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 4 noiembrie 2020 15:08:36
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 50002;

int n, m, grad[N], x[N];
vector <int> v[N];
bool marcat[N];

void citire() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);

        v[x].push_back(y);
        ++grad[y];
    }
}

void rez() {
    int p = 0, q = -1;

    for (int i = 1; i <= n; ++i)
        if (grad[i] == 0) {
            x[++q] = i;
            marcat[i] = true;
        }

    while (p <= q) {
        for (int i = 0; i < (int) v[x[p]].size(); ++i) {
            if (!marcat[v[x[p]][i]])
                --grad[v[x[p]][i]];

            if (grad[v[x[p]][i]] == 0 && !marcat[v[x[p]][i]]) {
                marcat[v[x[p]][i]] = true;
                x[++q] = v[x[p]][i];
            }
        }

        ++p;
    }

    for (int i = 0; i < p; ++i)
        printf("%d ", x[i]);
    printf("\n");
}

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

    citire();

    rez();

    return 0;
}