Simina: /* Date de ieșire */

2023-12-27T14:56:15Z

Date de ieșire

← Older revision		Revision as of 14:56, 27 December 2023
Line 6:		Line 6:

	= Date de ieșire =		= Date de ieșire =
	Fișierul de ieșire <code>subarbore1OUT.txt</code> va conține pe prima linie nodurile terminale din subarborele cu rădăcina în <code>k</code>, în ordine crescătoare, separate printr-un spațiu.		Fișierul de ieșire <code>subarbore1OUT.txt</code> va conține pe prima linie nodurile terminale din subarborele cu rădăcina în <code>k</code>, în ordine crescătoare, separate printr-un spaț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 =		= Restricții și precizări =

Simina: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu `n` noduri și un nod `k`. Afișați, în ordine crescătoare, nodurile terminale din subarborele cu rădăcina în `k`. = Date de intrare = Fișierul de intrare `subarbore1IN.txt` conține pe prima linie numărul de noduri `n` și nodul `k`. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații....

2023-12-26T23:28:15Z

Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Afișați, în ordine crescătoare, nodurile terminale din subarborele cu rădăcina în <code>k</code>. = Date de intrare = Fișierul de intrare <code>subarbore1IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații....

New page

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Afișați, în ordine crescătoare, nodurile terminale din subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarbore1IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</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>subarbore1OUT.txt</code> va conține pe prima linie nodurile terminale din subarborele cu rădăcina în <code>k</code>, în ordine crescătoare, separate printr-un spațiu.

= Restricții și precizări =

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

= Exemplul 1: =
<code>subarbore1IN.txt</code>
8 4
4 3 0 3 2 1 4 1
<code>subarbore1OUT.txt</code>
6 7 8

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def dfs(nod, lista_adiacenta, rezultat):
# Verificăm dacă nodul este terminal
if nod not in lista_adiacenta:
rezultat.append(nod)
return

# Parcurgem vecinii nodului și aplicăm DFS pe fiecare dintre ei
for vecin in lista_adiacenta[nod]:
dfs(vecin, lista_adiacenta, rezultat)

def verifica_restrictii(n, k):
if not (1 <= n <= 100 and 1 <= k <= n):
with open("subarbore1OUT.txt", 'w') as fisier:
fisier.write("Datele nu corespund restrictiilor impuse")
exit()

def main(fisier_intrare, fisier_iesire):
with open(fisier_intrare, 'r') as fisier:
# Citim numărul de noduri și nodul k
n, k = map(int, fisier.readline().split())

# Verificăm dacă restricțiile sunt respectate
verifica_restrictii(n, k)

# Citim vectorul de tați al arborelui
tati = list(map(int, fisier.readline().split()))

# Construim o listă de adiacență bazată pe vectorul de tați
lista_adiacenta = {}
for i in range(n):
parinte = tati[i]
if parinte not in lista_adiacenta:
lista_adiacenta[parinte] = []
lista_adiacenta[parinte].append(i + 1) # Adăugăm nodul curent ca fiu al nodului părinte

# Aplicăm DFS pentru a identifica nodurile terminale din subarborele cu rădăcina în nodul k
rezultat = []
dfs(k, lista_adiacenta, rezultat)

# Scriem rezultatul în fișierul de ieșire
with open(fisier_iesire, 'w') as fisier:
if not rezultat:
fisier.write("Subarborele nu are noduri terminale")
else:
fisier.write(' '.join(map(str, sorted(rezultat))))

# Exemplu de utilizare
main("subarbore1IN.txt", "subarbore1OUT.txt")

</syntaxhighlight>

0646 – Subarbore1 - Revision history

Simina: /* Date de ieșire */