h2. 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.

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

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 $x$ 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 $x$ 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

| 1 0 2 -1 1
|

h3. Explicatie

h2. Indicatii de rezolvare

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.

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$.

*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).

Mai multe detalii 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.

== include(page="template/taskfooter" task_id="bfs") ==