h2. Cerinta
Fiind dat un nod $S$, sa se determine, pentru fiecare nod $X$, numarul minim de arce ce trebuie parcurse pentru a ajunge din nodul sursa $S$ la nodul $X$.
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.
h2. Date de intrare
Fisierul de intrare $bfs.in$ contine pe prima linie 3 numere intregi $N M S$, cu semnificatia din enunt. Urmatoarele $M$ linii contin cate doua numere $x y$, cu semnificatia ca exista arc orientat de la $x$ la $y$.
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$.
h2. 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 $S$ la nodul $i$.
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$.
h2. Restrictii
* $2 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 1 000 000$
* Daca nu se poate ajunge din nodul $S$ la nodul $i$, atunci numarul corespunzator numarului $i$ va fi $-1$.
* Daca nu se poate ajunge din nodul $x$ la nodul $i$, atunci numarul corespunzator numarului $i$ va fi $-1$.
h2. Exemplu
table(example). |_. 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
| 5 7 1 5
1 2
2 3
2 4
3 2
3 5
4 3
4 5
| 4
1 2 3 5
|
h2. Indicatii de rezolvare
h3. Explicatie
Initial, se insereaza nodul $S$ 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 nou adaugat va fi costul nodului care l-a adaugat $+ 1$. Mai multe amanunte asupra algoritmului de parcurgere in latime ({_Breadth First Search_}) puteti gasi "aici":http://en.wikipedia.org/wiki/Breadth-first_search si "aici":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2.
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.
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 listelor de adiacenta, se gaseste 'aici':job_detail/223158?action=view-source.
*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).
Un alt algoritm pentru parcurgerea unui graf este prezentat 'aici':problema/dfs.
h2. Aplicatii
Algoritmul de parcurgere in latime ({_Breadth First Search_}) poate fi adaptat in multe probleme. De exemplu, la problema 'Muzeu':problema/muzeu putem consideram matricea data un graf in care celulele sunt noduri, iar laturile comune dintre celule sunt muchii. La problema "CrazySwitches":http://www.topcoder.com/stat?c=problem_statement&pm=6071&rd=9812, graful este reprezentat de stari binare, iar muchiile de posibilitatea de a ne deplasa dintr-o stare in alta. Un tip mai aparte de BFS, prezent si in problema anterioara, este acela cand costurile de pe muchii sunt mici si pentru a rezolva problema folosim mai multe cozi (complexitatea fiind mai mica decat daca am folosi algoritmul 'Dijkstra':problema/dijkstra). Mai multe explicatii asupra acestui procedeu gasiti in acest 'articol':preoni-2005/runda-2/solutii, la problema 'Car':problema/car. Alte probleme ce folosesc algoritmul de parcurgere in latime in rezolvare sunt:
* 'Graf':problema/graf
* 'Sate':problema/sate
* "Cadere":http://campion.edu.ro/problems/3/455/cadere_ro.htm
* "Honest":http://campion.edu.ro/problems/3/237/honest_ro.htm
* 'Padure':problema/padure
== include(page="template/taskfooter" task_id="bfs") ==
== include(page="template/taskfooter" task_id="bfs") ==
