De ce contează?
Un dispecer telefonic primește toată ziua aceeași întrebare: „pot suna de la centrala A la centrala B?”. Naiv, ar căuta de fiecare dată un traseu prin toată rețeaua de cabluri. Un dispecer isteț face altceva: o singură dată lipește pe fiecare centrală o etichetă cu numărul rețelei din care face parte. De atunci, orice întrebare are răspuns instant: se pot suna exact când etichetele coincid. Lecția asta e despre algoritmul care lipește etichetele.
Intuiția
Lecția despre conexitate te-a învățat ce este o componentă conexă: o insulă
maximală de noduri legate între ele. Aici învățăm algoritmul care le etichetează:
nu doar „am vizitat nodul" (un bool), ci „nodul acesta aparține componentei
numărul 1, acela componentei 2". Ținem un vector comp[] în care comp[nod] =
numărul componentei lui. Un 0 înseamnă „încă neetichetat". La final, cea mai
mare valoare din comp[] este chiar numărul de componente.
Puterea etichetei: după o singură etichetare în O(n+m), întrebarea „sunt u și
v în aceeași componentă?" nu mai cere nicio parcurgere — compari doar
comp[u] == comp[v], în O(1). La q = 100000 de întrebări pe un graf cu
n = 100000, diferența e între miliarde de pași (un BFS per întrebare) și
100000 de comparații.