0636 – Arbore

Cerința

Se dau cele n-1 muchii ale unui arbore cu n noduri și un nod k . Afișați vectorul de tați al arborelui cu rădăcina în k.

Date de intrare

Fișierul de intrare arboreIN.txt conține pe prima linie numerele n k, Următoarele n-1 linii vor conține câte o pereche i j, reprezentând muchiile arborelui.

Date de ieșire

Fișierul de ieșire arboreOUT.txt va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în k, 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

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

Exemplul 1 :

arboreIN.txt

7 4
1 2
1 4
1 7
3 7
5 7
6 7

arboreOUT.txt

4 1 7 0 7 7 1 

Exemplul 2 :

arboreIN.txt

1000 1001
1 2
1 4
1 7
3 7
5 7
6 7

arboreOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def verifica_restrictii(n, k, muchii):
    if not (1 <= n <= 100) or not (1 <= k <= n) or len(muchii) != n - 1:
        with open("arboreOUT.txt", "w") as file_out:
            file_out.write("Datele nu corespund restrictiilor impuse")
        return False
    # Verifică dacă nodurile din muchii sunt în intervalul corect
    for muchie in muchii:
        if not (1 <= muchie[0] <= n) or not (1 <= muchie[1] <= n):
            with open("arboreOUT.txt", "w") as file_out:
                file_out.write("Datele nu corespund restrictiilor impuse")
            return False
    return True

def dfs(nod, parinte, graf, rezultat):
    rezultat[nod] = parinte
    for vecin in graf[nod]:
        if vecin != parinte:
            dfs(vecin, nod, graf, rezultat)

def main():
    # Citirea datelor de intrare
    with open("arboreIN.txt", "r") as file_in:
        n, k = map(int, file_in.readline().split())
        muchii = [tuple(map(int, file_in.readline().split())) for _ in range(n - 1)]

    # Verificarea restricțiilor
    if not verifica_restrictii(n, k, muchii):
        return

    # Construirea grafului
    graf = {i: [] for i in range(1, n + 1)}
    for muchie in muchii:
        graf[muchie[0]].append(muchie[1])
        graf[muchie[1]].append(muchie[0])

    # Inițializarea vectorului de tați cu 0
    parinti = [0] * (n + 1)

    # Apelarea algoritmului DFS
    dfs(k, 0, graf, parinti)

    # Scrierea rezultatului în fișierul de ieșire
    with open("arboreOUT.txt", "w") as file_out:
        file_out.write(" ".join(map(str, parinti[1:])))

if __name__ == "__main__":
    main()