Bacalaureat · Grafuri și arbori · clasa a 12-a
Parcurgerea în adâncime (DFS)
Cerință
Afișează nodurile vizitate de parcurgerea în adâncime pornind din s. Din fiecare nod mergi mereu în cel mai mic vecin nevizitat.
Problemă originală de antrenament, nu este subiect oficial.
Date de intrare
Pe prima linie se află n și m (noduri, muchii). Pe următoarele m linii câte o muchie x y. Pe ultima linie se află s.
Date de ieșire
Nodurile vizitate, în ordinea vizitării. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ n ≤ 2000
- Sunt 20 de teste, fiecare valorează 5 puncte.
4 1 1 2 1
1 2
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Recursiv: vizitează nodul, apoi apelează DFS pentru fiecare vecin nevizitat, în ordine crescătoare. Rezultatul corect pentru acest exemplu este: 1 2.
6 8 4 5 1 5 2 5 3 4 2 6 1 2 2 3 5 6 4
4 3 2 1 5 6
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Recursiv: vizitează nodul, apoi apelează DFS pentru fiecare vecin nevizitat, în ordine crescătoare. Rezultatul corect pentru acest exemplu este: 4 3 2 1 5 6.
12 12 9 12 4 6 1 10 4 11 3 8 2 8 5 10 9 11 1 4 6 8 7 11 2 3 1
1 4 6 8 2 3 11 7 9 12 10 5
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Recursiv: vizitează nodul, apoi apelează DFS pentru fiecare vecin nevizitat, în ordine crescătoare. Rezultatul corect pentru acest exemplu este: 1 4 6 8 2 3 11 7 9 12 10 5.