0637 – Frunze

Cerinţa

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați rădăcina arborelui și frunzele acestuia.

Date de intrare

Fișierul de intrare frunzein.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 frunzeout.txt va conține pe prima linie rădăcina arborelui. A doua linia va conține numărul de frunze din arbore, iar următoarea linie frunzele, în ordine crescătoare și separate printr-un spațiu.

Restricții și precizări

• 1 ⩽ n ⩽ 100
• în vectorul de tați rădăcina este marcată cu 0

Exemplul 1

frunzein.txt

7
4 1 7 0 7 7 1

frunzeout.txt

Datele de intrare corespund restrictiilor impuse.
4
4
2 3 5 6  

Exemplul 2

frunzein.txt

jjgrgjrfrf

frunzeout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat

def validare(n_validare, tati_validare):

   # Verificăm dacă n este în intervalul 1-100
   if n_validare < 1 or n_validare > 100:
       raise ValueError  # Ridicăm o eroare dacă n nu este în intervalul 1-100
   # Verificăm dacă rădăcina este marcată cu 0 în vectorul de tați
   if 0 not in tati_validare:
       raise ValueError  # Ridicăm o eroare dacă rădăcina nu este marcată cu 0
   file_out.write("Datele de intrare corespund restrictiilor impuse.\n")

1. Funcția radacina_frunze determină rădăcina arborelui și frunzele acestuia

def radacina_frunze(n, tati):

   # Rădăcina arborelui este nodul care are tatăl 0
   radacina_tati = tati.index(0) + 1
   # Frunzele arborelui sunt nodurile care nu sunt tați pentru niciun nod
   frunze_tati = sorted(set(range(1, n + 1)) - set(tati))
   return radacina_tati, frunze_tati

if __name__ == '__main__':

   file_in = open("frunzein.txt", "r")
   file_out = open("frunzeout.txt", "w")

   try:
       # Citim numărul de noduri
       n_main = int(file_in.readline())
       # Citim vectorul de tați
       tati_main = list(map(int, file_in.readline().split()))
       # Validăm datele de intrare
       validare(n_main, tati_main)
       # Determinăm rădăcina arborelui și frunzele acestuia
       radacina, frunze = radacina_frunze(n_main, tati_main)
       # Scriem rădăcina și frunzele în fișierul de ieșire
       file_out.write(str(radacina) + '\n')
       file_out.write(str(len(frunze)) + '\n')
       file_out.write(' '.join(map(str, frunze)) + '\n')

   # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>