Задача «Родословная: подсчет уровней» Мое решение на Python 3.
Условие задачи:
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.
Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.
Вам дано генеалогическое древо, определите высоту всех его элементов.
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.
Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.
https://pythontutor.ru/lessons/dicts/problems/genealogy_ancestors_and_descendants/
Мое решение:
n = int(input()) # число строк ввода
A = dict() # словарь входных данных
B = dict() # словарь имен
C = dict() # конечный словарь (решение задачи)
for i in range(n-1):
temp = input().split()
A[temp[0]] = temp[1]
# сформировали словарь входных данных
B[temp[0]] = 0
B[temp[1]] = 0
# сформировали словарь всех имеющихся имен
# для учета какие имена уже посчитаны
parents = A.values()
# сформировали список родителей
childrens = A.keys()
# сформировали список родителей
for name in parents:
# перебираем имена отцов
# находим 0-ое поколение
if name not in childrens:
C[name] = 0
del B[name]
break # т.к. по задаче всего один родоначальник,
# поэтому выходим из цикла
count_generation = 0 # счетчик поколений
while len(B) > 0 : # прерывание по пустому словарю B
for key, val in A.items():
# перебираем имена в исзодном словаре
# находим n-ое поколение (у них родитель только 0-ое поколение)
try:
if C[val] == count_generation:
C[key] = count_generation + 1
del B[key]
except KeyError: continue
# если указанного имени нет в словаре С, то берем
# следующую пару
count_generation += 1 # увеличиваем счетчик поколений
# конец цикла
output = sorted(C.items())
C = dict(output)
# сортируем словарь С в алфавитном порядке
for key, val in C.items():
print(key, val)
# выводим отсортированный словарь С на экран
Если есть вопросы - пишите в комментариях, с радостью отвечу.
