0637 – Frunze

Cerinţa

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați rădăcina arborelui și frunzele acestuia.

Date de intrare

Fișierul de intrare frunzein.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 frunzeout.txt va conține pe prima linie rădăcina arborelui. A doua linia va conține numărul de frunze din arbore, iar următoarea linie frunzele, în ordine crescătoare și separate printr-un spațiu.

Restricții și precizări

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

Exemplul 1

frunzein.txt

7
4 1 7 0 7 7 1

frunzeout.txt

Datele de intrare corespund restrictiilor impuse.
4
4
2 3 5 6  

Exemplul 2

frunzein.txt

jjgrgjrfrf

frunzeout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

# Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat
def validare(n_validare, tati_validare):
    # Verificăm dacă n este în intervalul 1-100
    if n_validare < 1 or n_validare > 100:
        raise ValueError  # Ridicăm o eroare dacă n nu este în intervalul 1-100
    # Verificăm dacă rădăcina este marcată cu 0 în vectorul de tați
    if 0 not in tati_validare:
        raise ValueError  # Ridicăm o eroare dacă rădăcina nu este marcată cu 0
    file_out.write("Datele de intrare corespund restrictiilor impuse.\n")


# Funcția radacina_frunze determină rădăcina arborelui și frunzele acestuia
def radacina_frunze(n, tati):
    # Rădăcina arborelui este nodul care are tatăl 0
    radacina_tati = tati.index(0) + 1
    # Frunzele arborelui sunt nodurile care nu sunt tați pentru niciun nod
    frunze_tati = sorted(set(range(1, n + 1)) - set(tati))
    return radacina_tati, frunze_tati


if __name__ == '__main__':
    file_in = open("frunzein.txt", "r")
    file_out = open("frunzeout.txt", "w")

    try:
        # Citim numărul de noduri
        n_main = int(file_in.readline())
        # Citim vectorul de tați
        tati_main = list(map(int, file_in.readline().split()))
        # Validăm datele de intrare
        validare(n_main, tati_main)
        # Determinăm rădăcina arborelui și frunzele acestuia
        radacina, frunze = radacina_frunze(n_main, tati_main)
        # Scriem rădăcina și frunzele în fișierul de ieșire
        file_out.write(str(radacina) + '\n')
        file_out.write(str(len(frunze)) + '\n')
        file_out.write(' '.join(map(str, frunze)) + '\n')

    # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")