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.

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

<syntaxhighlight lang="python3"> 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()

</syntaxhighlight>