Rezolvare PBinfo #19

Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X.

Cerinţa

Să se afișeze vârfurile vizitate în urma parcurgerii în lățime (Breadth First Search) a grafului, pornind din vârful X.

Date de intrare

Fişierul de intrare BFS.in conţine pe prima linie trei numere naturale n m X, având următoarea semnificație: n este numărul de noduri, m este numărul de muchii din graf, iar X este vârful din care se începe parcurgerea. Următoarele m linii conțin câte două numere x y cu semnificația că există muchie între x și y .

Date de ieşire

Fişierul de ieşire BFS.out va conţine pe prima linie vârfurile vizitate în urma parcurgerii în lățime a grafului, aceasta începând din vârful X.

Restricţii şi precizări

• 2 ≤ n ≤ 100
• 1 ≤ m ≤ n*(n-1)/2
• Graful poate sa nu fie conex!!!
• dacă în timpul parcurgerii, la un moment dat vârful curent al grafului este Y, vecinii nevizitați ai lui Y se vor analiza în ordine crescătoare.

Exemplu:

BFS.in

5 7 2
1 2
3 2
1 5
2 4
3 1
4 5
5 3 

BFS.out

2 1 3 4 5