Editing 4159 – Nivele11 (section)

= Explicație =
Pe nivelul 0 se află rădăcina, adică nodul 3. Pe nivelul 1 se află nodurile 2 și 4 (descentenții direcți ai rădăcinii). Pe nivelul 2 se află nodurile 1, 5 și 7. Pe ultimul nivel se află nodurile 6 și 8.

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import defaultdict, deque

def verificare_restrictii(n):
    if 1 <= n <= 100:
        return True
    else:
        with open('nivele11OUT.txt', 'w') as file:
            file.write("Datele nu corespund restrictiilor impuse")
        return False

def parcurgere_pe_nivele(n, tati):
    if not verificare_restrictii(n):
        return []

    # Construim lista de adiacență pentru arbore
    graf = defaultdict(list)
    radacina = -1

    for i in range(n):
        parinte = tati[i]

        if parinte == 0:
            radacina = i + 1
        else:
            graf[parinte].append(i + 1)

    # Folosim BFS pentru a parcurge nodurile pe nivele
    nivele = []
    vizitat = [False] * (n + 1)
    queue = deque([(radacina, 0)])  # Rădăcina se află pe nivelul 0

    while queue:
        nod, nivel = queue.popleft()
        if not vizitat[nod]:
            vizitat[nod] = True

            # Adăugăm nodul la lista corespunzătoare nivelului său
            if len(nivele) <= nivel:
                nivele.append([])
            nivele[nivel].append(nod)

            # Adăugăm fiii nodului în coadă cu nivelul actual + 1
            for fiu in graf[nod]:
                if not vizitat[fiu]:
                    queue.append((fiu, nivel + 1))

    return nivele

# Citim datele din fișierul de intrare
with open('nivele11IN.txt', 'r') as file:
    n = int(file.readline().strip())
    tati = list(map(int, file.readline().strip().split()))

# Obținem rezultatul
rezultat = parcurgere_pe_nivele(n, tati)

# Dacă rezultatul nu este gol, scriem rezultatul în fișierul de ieșire
if rezultat:
    with open('nivele11OUT.txt', 'w') as file:
        for nivel in rezultat:
            file.write(' '.join(map(str, nivel)) + '\n')

</syntaxhighlight>