Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-11-26 00:10:07.
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 obtine 100 de puncte se poate gasi aici.

Un alt algoritm pentru parcurgerea unui graf este prezentat aici.

Probleme similare

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?