NézetNyomtat

Fagráf átmérője (Megoldas)
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok

Fagráf átmérője

Egy gráf átmérője a két legtávolabbi pont távolsága. Fagráfban bármely két csúcs között egyetlen út vezet, a csúcsok távolsága az út éleinek száma.
A fagráfot Prüfer-kód segítségével adhatjuk meg.

Feladat

Írj programot egy Prüfer-kóddal megadott fagráf átmérőjének kiszámítására.

Bemenet

A PRUFER.BE állomány sorai egy-egy gráfot adnak meg. Minden sorban az első szám a csúcsok $n$ száma, majd $n-2$ darab szám következik, a kód karakterei. Az utolsó teszteset után egy 0 zárja a bemeneti állományt.

Kimenet

A PRUFER.KI minden sorába a megfelelő teszteset gráfjának átmérőjét kell írni.

Példa

PRUFER.BEPRUFER.KI
8 1 2 1 3 3 5 0 5

Tesztadatok