Bacalaureat · Grafuri și arbori · clasa a 12-a
Parcurgerea în lățime (BFS)
Cerință
Afișează nodurile vizitate de parcurgerea în lățime pornind din nodul s. Vecinii unui nod se iau în ordine crescătoare.
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, separate prin spațiu. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ n ≤ 2000, 0 ≤ m ≤ 4000
- Sunt 20 de teste, fiecare valorează 5 puncte.
4 3 1 3 2 3 2 4 4
4 2 3 1
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Folosește o coadă; marchează nodul când îl pui în coadă. Rezultatul corect pentru acest exemplu este: 4 2 3 1.
6 3 1 3 1 5 4 6 6
6 4
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Folosește o coadă; marchează nodul când îl pui în coadă. Rezultatul corect pentru acest exemplu este: 6 4.
12 14 1 5 2 6 2 9 8 9 5 12 3 5 4 9 2 11 7 12 6 11 1 11 2 4 1 6 10 11 10
10 11 1 2 6 5 4 9 3 12 8 7
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Folosește o coadă; marchează nodul când îl pui în coadă. Rezultatul corect pentru acest exemplu este: 10 11 1 2 6 5 4 9 3 12 8 7.