De ce contează?
Imaginează-ți un oraș cu străzi cu sens unic. Vrei să găsești cartierele în care poți pleca de la orice intersecție și te poți întoarce mereu acasă. Faci două treceri prin oraș. La prima trecere te plimbi normal și notezi, pentru fiecare intersecție, momentul în care termini de explorat tot ce pleacă din ea. La a doua trecere mergi „pe contrasens" (toate străzile inversate), pornind din intersecțiile pe care le-ai terminat ultimele. Surpriza: pe contrasens nu mai poți ieși dintr-un cartier — fiecare plimbare îți desenează exact un cartier. Asta e Kosaraju-Sharir.
Intuiția
Vrem componentele tare conexe (CTC): grupuri maxime de noduri din care orice nod e accesibil din oricare altul. Problema e că un singur DFS naiv „curge" dintr-o CTC în alta și le amestecă. Kosaraju rezolvă asta cu un truc de ordine: un prim DFS care nu caută componente, ci doar stabilește în ce ordine se termină nodurile, apoi un al doilea DFS pe graful cu toate arcele inversate, care folosește acea ordine ca să se izoleze pe rând în câte o singură CTC.
Strânge fiecare CTC într-un singur „super-nod": graful rezultat (condensarea) e mereu un DAG — dacă ar avea un ciclu, CTC-urile de pe el s-ar uni într-una singură. Iar nodul cu cel mai mare timp de final la DFS1 stă garantat într-o CTC „sursă" a acestui DAG (în care nu intră niciun arc). Pe transpus, sursa devine „fundătură": un DFS pornit de acolo nu are pe unde să iasă din propria componentă. De aceea ordinea inversă a timpilor de final e exact prioritatea corectă.