0642 – Det Drum

Cerința

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Determinați drumul de la nodul k la rădăcina arborelui.

Date de intrare

Fișierul de intrare detdrumIN.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.

Date de ieșire

Fișierul de ieșire detdrumOUT.txt va conține pe prima linie nodurile care alcătuiesc drumul determinat, 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

detdrumIN.txt:

7 2

4 1 7 0 7 7 1

detdrumOUT.txt:

2 1 4

Exemplul 2

detdrumIN.txt:

101 2

4 1 7 0 7 7 1

detdrumOUT.txt:

Invalid input. Constraints not satisfied.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verify_constraints(n, k):

   return 1 <= n <= 100 and 1 <= k <= n

def solve_detdrum(n, k, t):

   a = [0] * 101
   rad = 0

   for i in range(1, n + 1):
       if t[i - 1] == 0:
           rad = i
       a[i] = t[i - 1]

   result = []

   def afis(x, a):
       nonlocal result
       if x != 0 and t[x - 1]:
           result.append(x)
           afis(t[x - 1], a)

   afis(k, a)
   result.append(rad)
   return result

if __name__ == "__main__":

   with open("detdrumIN.txt", "r") as infile, open("detdrumOUT.txt", "w") as outfile:
       n, k = map(int, infile.readline().split())

       if not verify_constraints(n, k):
           outfile.write("Invalid input. Constraints not satisfied.")
       else:
           t = list(map(int, infile.readline().split()))

           result = solve_detdrum(n, k, t)

           outfile.write(" ".join(map(str, result)))

</syntaxhighlight>