De ce contează?
Citești un enunț de olimpiadă: „Se dau n orașe și n - 1 șosele bidirecționale.
Din orice oraș se poate ajunge în oricare altul." Un concurent neantrenat vede „un
graf" și scoate artileria grea: detectare de cicluri, Dijkstra, structuri
complicate. Un olimpic vede două semnale — n - 1 și „conex" — și știe instant
că are în față un arbore. Din acea secundă problema s-a schimbat: drum unic între
oricare două orașe, rădăcină la alegere, DFS fără nicio grijă. Lecția asta îți
antrenează exact acest reflex de recunoaștere.
Ideea-cheie
Un arbore este un graf conex și fără cicluri. Multe enunțuri însă nu pronunță niciodată cuvântul „arbore" — îl ascund în spatele unei perechi de condiții: numărul de muchii și conexitatea. Cine recunoaște perechea primește gratuit o structură cu proprietăți mult mai puternice decât ale unui graf oarecare.
Dacă enunțul garantează conex și exact n - 1 muchii, graful este arbore —
fără nicio verificare suplimentară. Iar recunoașterea deblochează un arsenal întreg:
- între oricare două noduri există exact un drum — nu cauți „cel mai scurt", pentru că există unul singur;
- DFS/BFS nu pot întâlni cicluri — parcurgerea devine banală;
- poți alege o rădăcină arbitrară (tradițional, nodul 1) și gândi ierarhic, pe subarbori — poarta către DP pe arbore și LCA;
- diametrul iese din două BFS-uri, în
O(n).
De ce fix n - 1? E pragul exact: numărul minim de muchii ca graful să fie
conex (cu mai puține s-ar rupe în bucăți) și numărul maxim ca să nu apară
niciun ciclu (încă o muchie ar închide o buclă). Arborele stă fix pe acest prag.