Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-02 00:42:44.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:bfs.in, bfs.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deFlorianFlorian Marcu Florian
Timp execuţie pe test1.05 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

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.inbfs.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 listelor de adiacenta, se gaseste aici.

Un alt algoritm pentru parcurgerea unui graf este prezentat aici.

Aplicatii

Algoritmul de parcurgere in latime (Breadth First Search) poate fi adaptat intr-o multime de probleme. De exemplu, la problema Muzeu putem consideram matricea data un graf in care celulele sunt noduri, iar laturile comune dintre celule sunt muchii. La problema CrazySwitches de pe topcoder, 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. Mai multe explicatii asupra acestui procedeu gasiti in acest articol, la problema car. Alte probleme ce folosesc acest algoritm in rezolvare sunt:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?