Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bfs.in, bfs.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Florian Marcu •Florian |
| Timp execuţie pe test | 0.525 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
BFS - Parcurgere in latime
Se considera un graf orientat cu N varfuri si M arce.
Cerinta
Fiind dat un nod X, sa se determine, pentru fiecare nod, numarul minim de arce ce trebuie parcurse pentru a ajunge din nodul X la nodul respectiv.
Date de intrare
Fisierul de intrare bfs.in contine pe prima linie 3 numere intregi N M X, cu semnificatia din enunt. Urmatoarele M linii contin cate doua numere x $y, cu semnificatia ca exista arc orientat de la x la y.
Date de iesire
In fisierul de iesire bfs.out se vor afla N numere separate prin spatiu cu semnificatia ca al i-lea numar reprezinta numarul minim de arce ce trebuie parcurse de la nodul X la nodul i.
Restrictii
- 2 ≤ N ≤ 100 000
- 1 ≤ M ≤ 1 000 000
- Daca nu se poate ajunge din nodul X la nodul i, atunci numarul corespunzator numarului i va fi -1.
Exemplu
| bfs.in | bfs.out |
|---|---|
| 5 7 2 1 2 2 1 2 2 3 2 2 5 5 3 4 5 | 1 0 2 -1 1 |
Indicatii de rezolvare
Initial, se insereaza nodul X intr-o coada vida, cu costul 0. La fiecare pas, se ia nodul din inceputul cozii, se elimina si apoi se adauga vecinii nevizitati la finalul cozii. Costul unui nod adaugat = costul nodului care l-a adaugat + 1. Mai multe amanunte asupra algoritmului de parcurgere in latime (Breadth First Search) puteti gasi aici si aici.
O rezolvare ce foloseste o matrice de adiacenta pentru a retine graful obtine 50 de puncte. O solutie optima ca timp si memorie - O(N+M), implementata cu ajutorul unei liste de vecini, se gaseste aici.
Un alt algoritm pentru parcurgerea unui graf este prezentat aici.
