Detectarea unui ciclu într-un graf orientat
Un sistem de construire a proiectelor știe că pachetul A are nevoie de B, B de C, iar C... de A. Nimic nu mai poate fi construit primul. Un planificator de sarcini, un manager de pachete sau un calcul de foi de calcul (celule care se referă una la alta) trebuie să detecteze astfel de cicluri. Instrumentul: un DFS cu trei stări.
De ce nu ajunge „deja vizitat”
Într-un graf orientat poți ajunge într-un nod pe două drumuri diferite fără să existe vreun ciclu. Un DFS care declară ciclu la orice nod deja vizitat greșește:
# Graf orientat fără ciclu, dar cu două drumuri către același nod:
# 0 -> 1 -> 2 și 0 -> 2
graf = {0: [1, 2], 1: [2], 2: []}
vizitat = set()
Scrie funcția are_ciclu(n, muchii) pentru un graf orientat cu nodurile 0 .. n-1 (muchia [a, b] înseamnă a → b). Returnează True dacă graful are cel puțin un ciclu, folosind un DFS cu trei stări.
- Construiește graful orientat: doar graf[a].append(b).
- Ține o listă stare cu valorile NEVIZITAT / IN_CURS / TERMINAT.
- În DFS: o muchie către un nod IN_CURS înseamnă ciclu; la final nodul devine TERMINAT. Pornește DFS din fiecare nod nevizitat.
- Trebuie să apară: True, False, False, True, True, False.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan