6 подписчиков
Задача «Родословная: LCA». Мое решение на Python 3.
Условие
В генеалогическом древе определите для двух элементов их наименьшего общего предка (Lowest Common Ancestor). Наименьшим общим предком элементов A и B является такой элемент C, что С является предком A, C является предком B, при этом глубина C является наибольшей из возможных. При этом элемент считается своим собственным предком.
Формат входных данных аналогичен предыдущей задаче "Родословная: подсчет уровней".
Для каждого запроса выведите наименьшего общего предка данных элементов.
Решение:
k = int(input()) # число строк ввода
A = dict() # словарь запросов
for i in range(k-1):
temp = input().split()
A[temp[0]] = temp[1]
parents = A.values()
# сформировали список родителей
childrens = A.keys()
# сформировали список детей
for name in parents:
# перебираем имена отцов
# находим 0-ое поколение
if name not in childrens:
first = name
del name
break
k = int(input()) # число строк ввода
for i in range(k):
temp = input().split()
key = temp[0]
val = temp[1]
# сформировали пару
finally_output = []
# список для вывода на экран
key_parent = []
key_parent.append(key)
val_parent = []
val_parent.append(val)
в родословные самих участников
G = A.copy()
dad_key = G.get(key)
key_parent.append(dad_key)
dad_val = G.get(val)
val_parent.append(dad_val)
while dad_key != first:
dad_key = G.get(dad_key)
key_parent.append(dad_key)
# добавляем предков родственника key
1 минута
17 июля 2022