Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-11-25 23:34:54.
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

Explicatie

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.

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?