Cod sursa(job #2536328)

Utilizator MicuMicuda Andrei Micu Data 1 februarie 2020 20:07:04
Problema Sortare topologica Scor 40
Compilator py Status done
Runda Arhiva educationala Marime 0.77 kb
with open("sortaret.in") as fin:
    n, m = (int(x) for x in fin.readline().split())
    lst_ad = [[] for i in range(n+1)]
    lst_noduri = [i for i in range(1, n+1)]
    nr_pred = [0] * (n+1)
    for muchie in fin:
        i, j = (int(x) for x in muchie.split())
        lst_ad[i].append(j)
        nr_pred[j] += 1
q = []
for nod in lst_noduri:
    if not nr_pred[nod]:
        q.append(nod)
        lst_noduri.remove(nod)

rez = []
while q:
    nod_curent = q.pop(0)
    rez.append(nod_curent)
    for succ in lst_ad[nod_curent]:
        nr_pred[succ] -= 1

    for nod in lst_noduri:
        if not nr_pred[nod]:
            q.append(nod)
            lst_noduri.remove(nod)

with open("sortaret.out", 'w') as fout:
    fout.write(' '.join([str(x) for x in rez]))