De ce contează?
Un cuțit elvețian nu e o lamă care taie pâine — e o carcasă în care înfigi unealta de care ai nevoie: lamă, șurubelniță, foarfecă. DFS e la fel. Nu e „o plimbare prin graf" și atât; e o carcasă universală pe care o personalizezi adăugând două-trei linii. Aceeași recursie devine numărător de componente, detector de cicluri sau sortare topologică — în funcție de unealta pe care o înfigi în ea.
Ideea-cheie
Ai învățat DFS ca pe un algoritm care vizitează tot graful. Adevărul mai puternic e că DFS e un tipar, nu o singură rețetă. Scheletul lui are mereu trei locuri fixe în care se întâmplă ceva:
- la intrare în nod (înainte să cobori în vecini) — momentul pre-order;
- pe fiecare muchie către un vecin (când decizi dacă intri sau nu);
- la ieșire din nod (după ce toți vecinii au fost terminați) — momentul post-order.
Recursia care le leagă rămâne neschimbată. Ce schimbi de la o problemă la alta e doar ce cod pui în aceste trei locuri. Asta e cârligul.
Scheletul DFS e mereu același: marchează nodul, intră în fiecare vecin nevizitat, ieși. Puterea nu vine din recursie — recursia e doar carcasa. Vine din CE faci în cele trei momente: la intrare, pe muchie și la ieșire. Schimbi cârligul, schimbi problema rezolvată, fără să rescrii parcurgerea.
Iată carcasa goală, cu cele trei locuri marcate ca să o ai mereu în minte:
vector<int> adiacenta[100005];
bool vizitat[100005];
void dfs(int nod) {
vizitat[nod] = true;
// (A) LA INTRARE: pre-order — actiune cand AJUNGI in nod
for (int vecin : adiacenta[nod]) {
// (B) PE MUCHIE: decizi/observi muchia nod->vecin
if (!vizitat[vecin]) {
dfs(vecin);
}
}
// (C) LA IESIRE: post-order — actiune cand TERMINI nodul
}