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

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.

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.

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.

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 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 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 in multe 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, 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). Mai multe explicatii asupra acestui procedeu gasiti in acest articol, la problema Car. Alte probleme ce folosesc algoritmul de parcurgere in latime in rezolvare sunt:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content