Editing 0646 – Subarbore1 (section)

= Exemplul 2: =
<code>subarbore1IN.txt</code>
 101 2
 4 3 0 3 2 1 4 1
<code>subarbore1OUT.txt</code>
 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))))

# Exemplu de utilizare
main("subarbore1IN.txt", "subarbore1OUT.txt")

</syntaxhighlight>