Cod sursa(job #2756826)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 3 iunie 2021 08:40:44
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include<cstdio>
#include<vector>

using namespace std;

const int N = 50002;

int n, m, grad[N], x[N];
vector <int> v[N];
// pun pe 1 cand devine un nod cu grad intern 0
bool marcat[N];

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

    for (int i = 1; i <= m; ++i) {
//        citesc muchia orientata xy
        int x, y;
        scanf("%d%d", &x, &y);
//  lista de adiacenta, nodului x ii adaug toti vecinii
        v[x].push_back(y);
//        grad[y] va retine cate muchii intra
        ++grad[y];
    }
}

void rez() {
    int p = 0, q = -1;
// adaug in coada x toate nodurile care au gradul intern 0
    for (int i = 1; i <= n; ++i)
        if (grad[i] == 0) {
            x[++q] = i;
            marcat[i] = true;
        }
// cat timp coada nu e goala
    while (p <= q) {
//        trecem prin toti vecinii nodului
        for (int i = 0; i < (int) v[x[p]].size(); ++i) {
//            daca nu ajung la 0
            if (!marcat[v[x[p]][i]])
//                trec prin toti vecinii si scad cu 1 gradul sau de intrare
                --grad[v[x[p]][i]];

//          daca am ajuns la 0, il adaug in coada ca sa ii scad si vecinii lui 
            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;
}