Obchodzenie Drzewa Skokami
Limit pamięci: 32 MB
Grafem nazywamy każdą parę , w której jest
skończonym zbiorem elementów zwanych wierzchołkami grafu, a jest
podzbiorem zbioru wszystkich nieuporządkowanych par różnych wierzchołków.
Elementy zbioru nazywamy krawędziami grafu. Jeżeli dla każdej pary
różnych wierzchołków , istnieje dokładnie jeden ciąg
różnych wierzchołków taki, że
, oraz pary dla , to graf nazywamy
drzewem. O wierzchołkach , mówi się, że są odległe w
drzewie o .
Wiadomo, że drzewo o wierzchołkach ma dokładnie
krawędzi. Drzewo , którego wierzchołki są ponumerowane od
do , można jednoznacznie opisać, podając liczbę
wierzchołków , a następnie odpowiedni ciąg par liczb
naturalnych opisujący wszystkie jego krawędzie.
Dowolną permutację wierzchołków - to znaczy ciąg, w którym każdy wierzchołek
drzewa występuje dokładnie jeden raz - nazywamy porządkiem obchodzenia drzewa.
Jeżeli każde kolejne dwa wierzchołki w pewnym porządku są odległe w drzewie
co najwyżej o , to mówimy, że jest to porządek
obchodzenia drzewa ze skokiem .
Wiadomo, że dla każdego drzewa można wyznaczyć porządek jego obchodzenia ze
skokiem .
Przykład
Rysunek przedstawia drzewo o 7 wierzchołkach. Wierzchołki drzewa są
reprezentowane przez czarne kropki, a krawędzie przez odcinki łączące kropki.
To drzewo można obejść ze skokiem 3 odwiedzając jego wierzchołki w następującym
porządku: 7 2 3 5 6 4 1.
Zadanie
Ułóż program, który:
- wczytuje opis drzewa ze standardowego wejścia,
- znajduje jeden dowolny porządek obchodzenia tego drzewa ze skokiem
,
- zapisuje wyznaczony porządek na standardowym wyjściu.
Wejście
- W pierwszym wierszu standardowego wejścia jest zapisana liczba całkowita
dodatnia , nie większa niż - jest to liczba
wierzchołków drzewa.
- W każdym z kolejnych wierszy jest zapisana jedna para liczb
naturalnych oddzielonych pojedynczym odstępem, reprezentująca jedną krawędź
drzewa.
Wyjście
W kolejnych wierszach standardowego wyjścia należy zapisać numery kolejnych
wierzchołków w porządku obchodzenia drzewa ze skokiem trzy - każdą liczbę
należy zapisać w osobnym wierszu.
Przykład
Dla danych wejściowych:
7
1 2
2 3
2 4
4 5
5 6
1 7
poprawną odpowiedzią jest:
7
2
3
5
6
4
1
Autor zadania: Krzysztof Diks.