Родословная: подсчет уровней
Вы решили задачу. Теперь можно сравнить подходы.
Высота ребёнка на единицу больше высоты родителя.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Обход от корня
Корень — имя, которое не встречается ребёнком. От него распространяем известные уровни на детей.
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).
На что обратить внимание
- Корню соответствует уровень 0.
- Имена выводятся по алфавиту, а не по уровню.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.