De ce contează?
Imaginează-ți un oraș cu străzi cu sens unic. Un cartier de prieteni e un grup de case în care, plecând de la oricine, poți ajunge la oricine — și te poți mereu întoarce, urmând doar sensurile permise. Două case din cartiere diferite nu au mereu acest du-te-vino: poate ajungi la verișoara din celălalt capăt, dar nu te mai întorci la tine pe sens unic. Aceste cartiere „închise în ele însele" sunt componentele tare conexe ale orașului.
Intuiția
Definiția ai întâlnit-o în lecția Tare conexitate: o componentă tare conexă (CTC) e un grup maximal de noduri în care, pentru orice pereche, există drum în ambele sensuri. Aici o privim ca obiect algoritmic: de ce nodurile se împart curat în astfel de grupuri și ce fel de parcurgeri le pot descoperi — mecanica exactă rămâne pentru lecția următoare.
u și v sunt în aceeași CTC dacă și numai dacă există drum u → v ȘI
drum v → u. Un singur DFS din u NU e de ajuns: el răspunde doar la „unde
ajung?" — atinge și noduri din care nu te mai poți întoarce, deci
supraestimează componenta.
Relația „u și v sunt mutual accesibile" e reflexivă, simetrică și
tranzitivă — o relație de echivalență. De aceea CTC-urile formează o
partiție: clase disjuncte, fiecare nod în exact una.