Editing 4159 – Nivele11

== Enunț ==
Într-un arbore cu rădăcină, nivelul unui nod este lungime lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Afișați parcurgerea pe nivele a arborelui dat.

= Date de intrare =
Fișierul de intrare <code>nivele11IN.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.

= Date de ieșire =
Fișierul de ieșire <code>nivele11OUT.txt</code> va conține mai multe linii. Fiecare linie <code>i</code> conține, în ordine crescătoare, nodurile aflate pe nivelul <code>i-1</code>, separate prin câte un epațiu.

= Restricții și precizări =

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

= Exemplul 1: =
<code>nivele11IN.txt</code>
 8
 4 3 0 3 2 1 2 1
<code>nivele11OUT.txt</code>
 3 
 2 4 
 1 5 7 
 6 8 

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