De ce contează?
Imaginează-ți o rețea de insule legate prin poduri. Unele insule au mai multe poduri către vecini — dacă unul cade, mai există ocoluri. Dar există și poduri unice: singura legătură între două maluri. Dacă tai exact acel pod, malul de dincolo rămâne izolat de restul lumii. O punte într-un graf este fix acel pod critic: muchia a cărei eliminare rupe rețeaua în mai multe bucăți.
Intuiția
O punte (muchie critică) este o muchie care, dacă o ștergi, mărește numărul de componente conexe — rupe graful. Pe un graf cu cicluri, muchiile dintr-un ciclu nu sunt punți: ciclul oferă un ocol. Punțile sunt exact muchiile care nu fac parte din niciun ciclu: sunt singurul drum între cele două capete.
Ai întâlnit deja ideea disc/low la punctele de articulație (noduri
critice). Recapitulare într-o frază: disc[u] = momentul descoperirii lui u
în DFS, low[u] = cel mai mic disc atins din subarborele lui u folosind
oricâte muchii de arbore și o singură muchie de întoarcere. Punțile folosesc
același DFS și aceiași doi vectori — schimbă doar condiția cu care marchezi
critică o muchie, nu un nod.
Muchia de arbore (u, v), cu v copil al lui u, e punte exact când
low[v] > disc[u] — strict. Adică subarborele lui v nu are NICIO altă
cale înapoi spre u sau mai sus: singura legătură e chiar (u, v). Contrast
cu articulațiile, unde condiția e low[v] >= disc[u]: egalitatea („mă întorc
fix în u") face nodul u critic, dar muchia (u, v) are ocol — nu e punte.