De ce contează?
Imaginează-ți harta unei rețele de drumuri dintre orașe. Unele orașe sunt intersecții obișnuite: dacă le ocolești, tot ajungi unde voiai. Dar există orașe prin care trece SINGURUL drum ce leagă două regiuni — un pod natural. Dacă acel oraș se inundă, harta se rupe în două bucăți care nu mai comunică. În teoria grafurilor, un astfel de nod critic se numește punct de articulație: un nod a cărui ștergere mărește numărul de componente conexe.
Intuiția
Un punct de articulație e un nod „slab” al grafului: scoate-l (împreună cu muchiile lui) și graful se sparge în mai multe bucăți deconectate. Ca să le găsim pe toate dintr-o singură parcurgere, ne uităm la graf prin ochii unui DFS: parcurgerea desenează un arbore (muchiile pe care coboară), iar restul muchiilor devin muchii de întoarcere — scurtături care urcă spre strămoși. Un subarbore care are o astfel de scurtătură poate „ocoli” nodul de deasupra; unul care nu are, depinde total de el.
Un nod u (ne-rădăcină) e punct de articulație exact când are un fiu v în
arborele DFS al cărui subarbore nu poate „sări” peste u printr-o muchie de
întoarcere: low[v] >= disc[u]. Rădăcina e caz special — e critică doar dacă
are cel puțin 2 fii în arborele DFS.