Родословная: подсчет уровней
Высота ребёнка на единицу больше высоты родителя.
Как к ней подойти
Потренируйтесь хранить пары «ключ - значение» и находить нужные записи в словаре.
Словарь связывает ключ со значением и позволяет быстро найти запись по ключу. Решите, что будет ключом, что значением и как обрабатывать отсутствующую запись. Для подсчётов удобно начинать с нуля.
Корень — имя, которое не встречается ребёнком. От него распространяем известные уровни на детей.
Проверьте перед запуском
- Корню соответствует уровень 0.
- Имена выводятся по алфавиту, а не по уровню.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Обход от корня
Корень — имя, которое не встречается ребёнком. От него распространяем известные уровни на детей.
n = int(input())
parent = {}
children = {}
for _ in range(n - 1):
child, ancestor = input().split()
parent[child] = ancestor
children.setdefault(ancestor, []).append(child)
children.setdefault(child, [])
root = next(name for name in children if name not in parent)
level = {root: 0}
order = [root]
for name in order:
for child in children[name]:
level[child] = level[name] + 1
order.append(child)
for name in sorted(level):
print(name, level[name])
Время: O(n log n) с сортировкой вывода; обход O(n). Память: O(n).
Другой способ: Подсчёт длины каждой цепочки
Для каждого имени отдельно считаем переходы к родителям до корня. Это допустимый учебный O(n²) подход.
n = int(input())
parent = {}
children = {}
for _ in range(n - 1):
child, ancestor = input().split()
parent[child] = ancestor
children.setdefault(ancestor, []).append(child)
children.setdefault(child, [])
for name in sorted(children):
current = name
level = 0
while current in parent:
current = parent[current]
level += 1
print(name, level)
Время: O(nh + n log n), h — высота. Память: O(n).