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.

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

<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

1. 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()))

1. Obținem rezultatul

rezultat = parcurgere_pe_nivele(n, tati)

1. 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>