Rezolvare PBinfo #539

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 adâncime (Depth First Search) a grafului, pornind din vârful X.

Date de intrare

Fişierul de intrare dfs.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 i j cu semnificația că există muchie între i și j .

Date de ieşire

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

Restricţii şi precizări

• 2 ≤ n ≤ 100
• 1 ≤ m ≤ n*(n-1)/2
• 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:

dfs.in

7 8 3
1 2
1 3
1 6
2 4
2 5
3 6
3 7
4 6

dfs.out

3 1 2 4 6 5 7