0646 – Subarbore1

Cerința

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Afișați, în ordine crescătoare, nodurile terminale din subarborele cu rădăcina în k.

Date de intrare

Fișierul de intrare subarbore1IN.txt conține pe prima linie numărul de noduri n și nodul k. 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 subarbore1OUT.txt va conține pe prima linie nodurile terminale din subarborele cu rădăcina în k, în ordine crescătoare, separate printr-un spațiu.Î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
• 1 ≤ k ≤ n
• în vectorul de tați rădăcina este marcată cu 0

Exemplul 1:

subarbore1IN.txt

8 4
4 3 0 3 2 1 4 1

subarbore1OUT.txt

6 7 8

Exemplul 2:

subarbore1IN.txt

101 2
4 3 0 3 2 1 4 1

subarbore1OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def dfs(nod, lista_adiacenta, rezultat):

   # Verificăm dacă nodul este terminal
   if nod not in lista_adiacenta:
       rezultat.append(nod)
       return
   
   # Parcurgem vecinii nodului și aplicăm DFS pe fiecare dintre ei
   for vecin in lista_adiacenta[nod]:
       dfs(vecin, lista_adiacenta, rezultat)

def verifica_restrictii(n, k):

   if not (1 <= n <= 100 and 1 <= k <= n):
       with open("subarbore1OUT.txt", 'w') as fisier:
           fisier.write("Datele nu corespund restrictiilor impuse")
       exit()

def main(fisier_intrare, fisier_iesire):

   with open(fisier_intrare, 'r') as fisier:
       # Citim numărul de noduri și nodul k
       n, k = map(int, fisier.readline().split())

       # Verificăm dacă restricțiile sunt respectate
       verifica_restrictii(n, k)
       
       # Citim vectorul de tați al arborelui
       tati = list(map(int, fisier.readline().split()))

   # Construim o listă de adiacență bazată pe vectorul de tați
   lista_adiacenta = {}
   for i in range(n):
       parinte = tati[i]
       if parinte not in lista_adiacenta:
           lista_adiacenta[parinte] = []
       lista_adiacenta[parinte].append(i + 1)  # Adăugăm nodul curent ca fiu al nodului părinte

   # Aplicăm DFS pentru a identifica nodurile terminale din subarborele cu rădăcina în nodul k
   rezultat = []
   dfs(k, lista_adiacenta, rezultat)

   # Scriem rezultatul în fișierul de ieșire
   with open(fisier_iesire, 'w') as fisier:
       if not rezultat:
           fisier.write("Subarborele nu are noduri terminale")
       else:
           fisier.write(' '.join(map(str, sorted(rezultat))))

1. Exemplu de utilizare

main("subarbore1IN.txt", "subarbore1OUT.txt")

</syntaxhighlight>