0639 – Înălțime
Enunț
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul 1
, fiii rădăcinii pe nivelul 2
, fiii fiilor rădăcinii pe nivelul 3
, etc. Numărul de nivele distincte din arbore determină înălțimea arborelui.
Cerința
Se dă vectorul de tați al unui arbore cu rădăcină cu n
noduri. Determinați înălțimea arborelui.
Date de intrare
Fișierul de intrare inaltimeIN.txt
conține pe prima linie numărul de noduri n
. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații.
Date de ieșire
Fișierul de ieșire inaltimeOUT.txt
va conține pe prima linie numărul H
, reprezentând înălțimea arborelui.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".
Restricții și precizări
1 ≤ n ≤ 100
- în vectorul de tați rădăcina este marcată cu
0
Exemplu 1:
inaltimeIN.txt
7 4 1 7 0 7 7 1
inaltimeOUT.txt
4
Exemplu 2:
inaltimeIN.txt
101 4 1 7 0 7 7 1
inaltimeOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
def verifica_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open("inaltimeOUT.txt", "w") as file:
file.write("Datele nu corespund restrictiilor impuse")
return False
def calculeaza_inaltimea(n, tati):
if not verifica_restrictii(n):
return
inaltime = 0
nivele = [0] * n
for i in range(n):
nivel = 0
j = i
while tati[j] != 0:
nivel += 1
j = tati[j] - 1
if nivele[j] != 0:
nivel += nivele[j]
break
nivele[i] = nivel
inaltime = max(inaltime, nivel + 1)
with open("inaltimeOUT.txt", "w") as file:
file.write(str(inaltime))
def main():
# Citirea datelor de intrare
with open("inaltimeIN.txt", "r") as file:
n = int(file.readline())
if not verifica_restrictii(n):
return
tati = list(map(int, file.readline().split()))
# Calcularea inaltimii arborelui
calculeaza_inaltimea(n, tati)
if __name__ == "__main__":
main()