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 0, fiii rădăcinii pe nivelul 1, fiii fiilor rădăcinii pe nivelul 2, etc.

Cerința

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

Date de intrare

Fișierul de intrare nivele11IN.txt conține pe prima linie numărul de noduri n. 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 nivele11OUT.txt va conține mai multe linii. Fiecare linie i conține, în ordine crescătoare, nodurile aflate pe nivelul i-1, separate prin câte un epaț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

• 1 ≤ n ≤ 100
• în vectorul de tați rădăcina este marcată cu 0

Exemplul 1:

nivele11IN.txt

8
4 3 0 3 2 1 2 1

nivele11OUT.txt

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:

nivele11IN.txt

101
4 3 0 3 2 1 2 1

nivele11OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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')