@SteppenHorde
Только постигаю азы программирования Python

Как для каждой вершины дерева правильно найти число её потомков?

Всем привет! Вот текст задачи:
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель. Для каждого элемента дерева определите число всех его потомков (не считая его самого).

Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

Примечание
Решение должно иметь сложность O(N), не считая сложности обращения к элементам словаря и сортировки результата.
P.S. Хоть какое-нибудь верное решение
Выходные данные
Выведите список всех элементов в лексикографическом порядке, для каждого элемента выводите количество всех его потомков.
Примеры
Примеры
входные данные
9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
выходные данные
Alexander_I 0
Alexei 1
Anna 4
Elizabeth 0
Nicholaus_I 0
Paul_I 2
Peter_I 8
Peter_II 0
Peter_III 3



Тема "словари", собственно, решал через них, ввод-вывод через файлы. Проблему описал в комментариях к коду.
Если не понятно объяснил, то вот pythontutor, там пошагово можно увидеть, что рекурсия завершается раньше, чем надо.
Мой код
def descendants(man):
# организую рекурсию по каждому элементу дерева, т.к. формат: предок:список непосредственных потомков, то у каждого
# ключа есть список из его непосредственных потомков, вот по ним и иду циклом for и считаю число потомков
# беда в том, что функция возвращает число потомков только в первой итерации for, не проходя по другим элементам в списке
# т.е. в списке ['Alexei', 'Anna', 'Elizabeth'] она пройдёт только по 'Alexei' (станет искать по этому ключу)
    if man in tree:
        for descendant in tree[man]:
            return 1 + descendants(descendant)
    else:
        return 0
        

inp_file = open('input.txt', 'r')
out_file = open('output.txt', 'w')

tree = {}
persons = set()

for i in range(int(inp_file.readline().rstrip()) - 1):
    # построчно считываем файл, добавляем в словарь в формате: предок:список непосредственных потомков
    descendant, parent = inp_file.readline().rstrip().split()
    persons.add(descendant) # для того, чтобы выводить каждую вершину отдельно и без повторов
    persons.add(parent)
    tree[parent] = tree.get(parent, [])
    tree[parent].append(descendant)

for man in sorted(list(persons)): # вывод
    out_file.write(man + str(descendants(man)) + ' ' + '\n')

inp_file.close()
out_file.close()
Заранее спасибо!
  • Вопрос задан
  • 186 просмотров
Пригласить эксперта
Ответы на вопрос 1
@tomatho
Обычный DFS (Depth First Search - Поиск в глубину)
Как именно? Сами подумайте.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы
14 авг. 2018, в 22:43
350 руб./за проект
14 авг. 2018, в 19:03
10000 руб./за проект
14 авг. 2018, в 18:10
1000 руб./в час