避免从子父关系生成字典时出现循环

Question

我正在尝试根据子父关系创建一棵字典树，但这里的问题是子节点可以包含他的前辈之一，从而生成我想避免的循环。

list_child_parent = [(2,1),(3,2),(4,2),(5,3),(6,4),(2,6)]
def make_map(list_child_parent):
    has_parent = set()
    all_items = {}
    for child, parent in list_child_parent:
        if parent not in all_items:
            all_items[parent] = {}
        if child not in all_items:
            all_items[child] = {}
        
        if parent not in all_items[child]:
            all_items[parent][child] = all_items[child]
            has_parent.add(child)
        else:
            continue

    result = {}
    for key, value in all_items.items():
        if key not in has_parent:
            result[key] = value
    return result
make_map(list_child_parent)

如果儿子包含他的父亲，则代码运行良好，但如果是祖父，则代码运行良好......
我认为需要另一种方法。

如果有意义的话，预期结果可以是任何结果：

{1: {2: {3: {5: {}}, 4: {6: {}}}}}

{1: {2: {3: {5: {}}, 4: {6: 2}}}}

{1: {2: {3: {5: {}}, 4: {6: {2:{}}}}}}

目前的结果是：

{1: {2: {3: {5: {}}, 4: {6: {2: {...}}}}}}

Answer 1

您可以使用集合来跟踪所有子级，这样如果当前子级以前是另一个父级的子级，则可以将后代的字典设置为空字典：

def make_map(list_child_parent):
    mapping = {}
    children = set()
    for child, parent in list_child_parent:
        mapping.setdefault(parent, {})[child] = (
            {} if child in children
            else mapping.setdefault(child, {})
        )
        children.add(child)
    return {
        parent: descendants
        for parent, descendants in mapping.items()
        if parent not in children
    }