De ce contează?
Imaginează-ți o hartă cu zeci de orașe legate prin drumuri cu sens unic. Unele grupuri de orașe sunt atât de bine conectate încât poți circula liber în interior, înainte și înapoi — ca un cartier cu străzi în buclă. Dacă desenezi fiecare astfel de grup ca un singur punct pe hartă, rămâne o rețea mult mai simplă: doar drumuri care merg „înainte”, fără nicio buclă mare. Exact asta face graful condensat.
Intuiția
Într-un graf orientat, o componentă tare conexă (CTC) e un grup de noduri din care poți ajunge din oricare în oricare altul. În interiorul ei există cicluri — și ciclurile sunt exact ce strică orice ordine pe un graf. Ideea e simplă: dacă comasezi fiecare CTC într-un singur super-nod, ciclurile interne dispar (sunt ascunse înăuntru), iar ce rămâne între super-noduri este garantat fără cicluri — adică un DAG (graf orientat aciclic). Pe un DAG poți face sortare topologică, programare dinamică pe noduri, drumuri — lucruri imposibile când ai cicluri.
De ce nu poate avea graful condensat niciun circuit? Presupune prin absurd că ar
exista unul: C_a → C_b → ... → C_a. Atunci, urmărind arcele în graful original,
orice nod din C_a ajunge la orice nod din C_b și înapoi — toate nodurile acestor
componente se ajung reciproc, deci ar forma prin definiție o singură CTC, nu mai
multe. Contradicție cu maximalitatea componentelor: condensarea dă mereu un DAG.