Programozó versenyek

Programozási technológiák pótZH 2014-04-10 Cs18

2014. április 10. 18:20 – 2014. április 10. 20:45

Fa

A gráfelméletben fának vagy fagráfnak nevezzük azokat a gráfokat, amelynek bármely két csúcsát pontosan egy út köti össze, azaz a fák körmentes összefüggő gráfok. Tekintsük a következő fa reprezentációt: A fák csúcsait egyetlen karakter jelöli, mely egyedi. Jelölje XY karakter pár, hogy egy adott fában X csúcsból Y csúcsba él vezet.

A fenti fa éleit az alábbi sor írja le: AB AC BD BE CF FG FH Az élek sorrendje nem számít, és mivel a fák irányítatlan fák a karakter párokban sem számít a csúcsokat reprezentáló karakterek sorrendje. A fenti sorral ekvivalens a következő: HF GF CF BD CA BA

A bemenet specifikációja

A bemeneten állományvégjelig tetszőleges számú teszteset érkezik. Minden teszteset két sorból áll. Az első sorban egyetlen karakter található, mely a fa gyökércsúcsát jelöli, ezt egyetlen sor követi, melyben, tetszőlegesen sok karakter pár található, ez a sor leír egy teljes fát.

A kimenet specifikációja

A kimeneten minden tesztesethez tartozóan pontosan egy sor jelenik meg, amelyben egyetlen egész érték a bemeneten szereplő leghosszabb út hosszát adja meg.

Példa bemenet

  1. A
  2. AB AC CD
  3. A
  4. AB AC BD BE CF FG FH
letöltés szöveges állományként

Példa kimenet

  1. 2
  2. 3
letöltés szöveges állományként
Debreceni Egyetem, Informatikai Kar, v. 2018.03.19.