Count descendants

count_descendants.py

class Cls:
    def __init__(self, name, parents):
        self.name = name
        self.parents = parents
        self.children = []
        self.descendents = set()

    def attach_parents(self, tree):
        for parent in self.parents:
            tree[parent].children.append(self)

    def dive(self) -> set:
        if self.descendents:
            return self.descendents
        self.descendents = {self}
        for child in self.children:
            self.descendents.update(child.dive())
        return self.descendents


def task(definitions):
    tree = {}
    for definition in definitions:
        cls = Cls(
            name=definition["name"],
            parents=definition["parents"]
        )
        tree[cls.name] = cls

    for cls in tree.values():
        cls.attach_parents(tree)

    for root in tree.values():
        root.dive()

    for name, cls in sorted(tree.items()):
        print(name, len(cls.descendents))


task([
    {"name": "A", "parents": []},
    {"name": "B", "parents": ["A", "C"]},
    {"name": "C", "parents": ["A"]}
])

print()
task([
    {"name": "B", "parents": ["A", "C"]},
    {"name": "C", "parents": ["A"]},
    {"name": "A", "parents": []},
    {"name": "D", "parents": ["C", "F"]},
    {"name": "E", "parents": ["D"]},
    {"name": "F", "parents": []},
])