Vizualizare sursă pentru „0638 – Nivele”

== Enunț ==
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri din arbore. Determinați pentru fiecare dintre cele <code>k</code> noduri nivelul pe care se află.

= Date de intrare =
Fișierul de intrare <code>niveleIN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. Linia a treia conține numărul <code>k</code>, iar linia a patra <code>k</code> noduri, <code>x[1]</code>, <code>x[2]</code>, … , <code>x[k]</code>.

= Date de ieșire =
Fișierul de ieșire <code>niveleOUT.txt</code> va conține <code>k</code> linii. Linia <code>i</code> va conține nivelul pe care se află nodul <code>x[i]</code> în arborele dat

= Restricții și precizări =

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

= Exemplul 1: =
<code>niveleIN.txt</code>
 7
 4 1 7 0 7 7 1 
 4
 1 3 4 7
<code>niveleOUT.txt</code>
 2
 4
 1
 3 

= Exemplul 2: =
<code>niveleIN.txt</code>
 101
 4 1 7 0 7 7 1 
 4
 1 3 4 7
<code>niveleOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, k, tati):
    if not(1 <= k <= n <= 100) or tati.count(0) != 1:
        with open("niveleOUT.txt", "w") as f_out:
            f_out.write("Datele nu corespund restrictiilor impuse")
        return False
    return True

def determina_nivelul(n, tati, k, noduri):
    # Verificare pentru restricții
    if not verifica_restrictii(n, k, tati):
        return

    nivele = [0] * n  # nivelele pentru fiecare nod
    radacina = tati.index(0) + 1  # găsim poziția rădăcinii în vectorul de tați

    def dfs(nod, nivel):
        nivele[nod - 1] = nivel  # nodurile sunt numerotate de la 1, așa că indexăm cu nod-1
        for fiu in range(1, n + 1):
            if tati[fiu - 1] == nod:
                dfs(fiu, nivel + 1)

    dfs(radacina, 1)

    rezultate = [nivele[nod - 1] for nod in noduri]

    # Scrierea rezultatelor în fișierul de ieșire
    with open("niveleOUT.txt", "w") as f_out:
        for rezultat in rezultate:
            f_out.write(str(rezultat) + "\n")

# Citirea datelor de intrare
with open("niveleIN.txt", "r") as f:
    n = int(f.readline().strip())
    tati = list(map(int, f.readline().split()))
    k = int(f.readline().strip())
    noduri = list(map(int, f.readline().split()))

# Determinarea nivelului pentru fiecare nod dat
determina_nivelul(n, tati, k, noduri)

</syntaxhighlight>