Sortarea topologică (algoritmul lui Kahn)
Dimineața nu poți încălța pantofii înaintea șosetelor. Un șantier nu ridică acoperișul înaintea pereților. Un compilator nu poate compila un modul înaintea celor de care depinde. Sortarea topologică găsește o ordine care respectă toate dependențele, iar algoritmul lui Kahn o construiește luând, pe rând, ce nu mai are nimic de așteptat.
Problema
Primești un graf orientat în care muchia a → b înseamnă „a trebuie înaintea lui b”. Vrei o listă cu toate nodurile în care fiecare muchie merge de la stânga la dreapta. O astfel de ordine există doar dacă graful nu are cicluri (DAG, *directed acyclic graph*).
# Dimineața: fiecare pereche (a, b) înseamnă „a trebuie făcut înainte de b”
reguli = [('chiloți', 'pantaloni'), ('pantaloni', 'pantofi'), ('șosete', 'pantofi'), ('cămașă', 'cravată')]
grad_intrare = {}
for a, b in reguli:
grad_intrare.setdefault(a, 0)
grad_intrare[b] = grad_intrare.get(b, 0) + 1 Scrie funcția ordine_topologica(n, muchii) pentru nodurile 0 .. n-1, unde [a, b] înseamnă „a înaintea lui b”. Folosește algoritmul lui Kahn cu un heap (la fiecare pas, cel mai mic nod disponibil). Dacă graful are un ciclu, returnează [].
- Construiește graful și lista grad (gradele de intrare).
- Pune în heap nodurile cu gradul 0, apoi scoate-le pe rând cu heappop și scade gradele vecinilor.
- Dacă la final ordinea are mai puțin de n noduri, întoarce [].
- Trebuie să apară: [4, 5, 0, 2, 3, 1], [], [0, 1, 2], [3, 2, 1, 0], [].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan