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 1 5 1 2 2 3 2 4 3 2 3 5 4 3 4 5 | 4 1 2 3 5 |
Explicatie
Un alt drum de lugime 4 poate fi 1 2 4 5. Un alt drum posibil de la varful 1 la varful 5 este 1 2 4 3 5, dar acesta nu are lungime minima.
Feedback Cosmin: de ce nu sunt n si m aici mult mai mari? Algoritmul de cautare in latime are complexitate O(n + m) si atunci ar merge date cu cateva ordine mai mari de marime decat cum sunt restrictiile acum.
Florian: Problema nu e inca finalizata. Nu e suficient 1000 de noduri si 100.000 de muchii?
astronomy: am lasat si eu un feedback sa fie data la n+m, cine l-a sters?:) Florian, daca dai N=1000 de noduri o sa intre N^2
Florian: Scuze. Eu l`am sters. Crezusem ca rezolvasem daca am marit N de la 100 la 1000. A fost neatentia mea. Voi pune N=100.000 si M=200.000.
Cosmin O sugestie: da testele gradat, pana la n = 1000 50 de puncte ca sa poata face toata lumea cu matrice de adiacenta in O(n^2). Si restul de 50 de puncte cu n si m mari ca sa trebuiasca sa folosesti liste de vecini si sa faci algoritmul in O(n + m).
