Vizualizare sursă pentru „0646 – Subarbore1”

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

= Date de intrare =
Fișierul de intrare <code>subarbore1IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. 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 <code>subarbore1OUT.txt</code> va conține pe prima linie nodurile terminale din subarborele cu rădăcina în <code>k</code>, î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 =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ k ≤ n</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>

= Exemplul 1: =
<code>subarbore1IN.txt</code>
 8 4
 4 3 0 3 2 1 4 1
<code>subarbore1OUT.txt</code>
 6 7 8

= 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>