Задача «Родословная: подсчет уровней»

Условие

В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.

Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.

Вам дано генеалогическое древо, определите высоту всех его элементов.

Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.

Примечание

Эта задача имеет решение сложности O(n), но вам достаточно написать решение сложности O(n2) (не считая сложности обращения к элементам словаря).

Решение

  1. def height(man):
  2.     if man not in p_tree:
  3.         return 0
  4.     else:
  5.         return 1 + height(p_tree[man])
  6. p_tree = {}
  7. n = int(input())
  8. for i in range(n - 1):
  9.     child, parent = input().split()
  10.     p_tree[child] = parent
  11. heights = {}
  12. for man in set(p_tree.keys()).union(set(p_tree.values())):
  13.     heights[man] = height(man)
  14. for key, value in sorted(heights.items()):
  15.     print(key, value)