Python 3. Задача «Родословная: предки и потомки». Мое решение.
Условие задачи:
https://pythontutor.ru/lessons/dicts/problems/genealogy_ancestors_and_descendants/
"Даны два элемента в дереве. Определите, является ли один из них потомком другого.
Во входных данных записано дерево в том же формате, что и в предыдущей задаче Далее идет число запросов K. В каждой из следующих K строк, содержатся имена двух элементов дерева.
Для каждого такого запроса выведите одно из трех чисел: 1, если первый элемент является предком второго, 2, если второй является предком первого или 0, если ни один из них не является предком другого."
Решение:
# изначально нам известно число строк в словаре исходных данных
k = int(input()) # число строк ввода
A = dict() # словарь запросов
# циклом формируем словарь исходных данных
for i in range(k-1):
temp = input().split()
A[temp[0]] = temp[1]
k = int(input()) # число строк ввода
B = dict() # словарь запросов
for i in range(k):
temp = input().split()
B[temp[0]] = temp[1]
# вторым циклом сформировали словарь запросов
parents = A.values()
# сформировали список родителей
childrens = A.keys()
# сформировали список детей
for name in parents:
# перебираем имена отцов
# находим основателя рода
if name not in childrens:
first = name
del name
break
for key, val in B.items():
status = 0 # конечный результат
G = A.copy()
# создаем временный словарь для поиска
if key == first:
status = 1
print(status)
continue
# основатель рода является предком для всех
if val == first:
status = 2
print(status)
continue
# основатель рода является предком для всех
else:
# если нет прямой пары наследник - потомок и нет основателя рода
dad_key = G.pop(key) # родитель первого из рассматриваемой пары
dad_val = G.pop(val) # родитель второго из рассматриваемой пары
# вытащили предков из словаря G и удалили их строки методом pop
# первый раз команда всегда выполняется, т.к. идет после проверки
if dad_key == first:
while dad_val != first and len(G) > 0:
if A[dad_val] == key:
status = 1
print(status)
break
# второй является предком первого
else: dad_val = G.pop(dad_val)
# если в паре оказались, что не родственники:
if status == 1: continue # переходим к следующей паре
if status == 0:
print(status)
continue
if dad_val == first and status == 0:
while dad_key != first and len(G) > 0:
if A[dad_key] == val:
status = 2
print(status)
break
# второй является предком первого
else: dad_key = G.pop(dad_key)
# если цикл пройден, то не пара не родственники, выводим "0"
if status == 1: continue # переходим к следующей паре
if status == 0:
print(status)
continue
# если в паре оба младше второго поколения
while dad_key != first and len(G) > 0 and status == 0:
if A[dad_key] == val:
status = 2
print(status)
break
# второй является предком первого
else: dad_key = G.pop(dad_key)
# перебираем предков первого
# пока не найдем второго или основателя рода
# если не нашли, то обновляем словарь G и родителей пары
G = A.copy()
dad_key = G.pop(key)
dad_val = G.pop(val)
# и ищем дальше
while dad_val != first and len(G) > 0 and status == 0:
if A[dad_val] == key:
status = 1
print(status)
break
# второй является предком первого
else: dad_val = G.pop(dad_val)
# перебираем предков первого
# пока не найдем первого или основателя рода
if status < 1: print(status)
# если не нашли родственника, то выводим 0, конец цикла
P.S. если есть вопросы пишите комментарии, всем с радостью отвечу
