带迭代首选规则的二分图环检测Python代码修复求助

你的代码核心问题在于环检测逻辑错误，以及对matched集合的滥用——它同时承担了"已处理参与者"和"已选择对象"的职责，导致环的识别不符合规则。以下是符合需求的列表嵌套列表版本代码，能正确输出预期的环：

def find_and_remove_cycles(preferences):
    # 用集合维护当前活跃的参与者（0-based索引）
    active = set(range(len(preferences)))
    cycles = []
    
    while True:
        # 构建当前迭代的首选映射：每个活跃参与者指向偏好列表中第一个仍在活跃的对象
        preference_map = {}
        for person in active:
            for choice in preferences[person]:
                if choice in active:
                    preference_map[person] = choice
                    break
        
        # 在当前映射中查找环
        visited = set()
        current_cycle = None
        
        for person in active:
            if person not in visited:
                path = []
                current = person
                while True:
                    # 无首选则无法形成环
                    if current not in preference_map:
                        break
                    # 已访问过，检查是否在当前路径中
                    if current in visited:
                        if current in path:
                            # 提取环：从重复节点到路径末尾
                            idx = path.index(current)
                            current_cycle = path[idx:]
                        break
                    visited.add(current)
                    path.append(current)
                    current = preference_map[current]
            # 找到环后立即退出遍历
            if current_cycle:
                break
        
        # 无环可找时终止循环
        if not current_cycle:
            break
        
        # 转换为1-based编号（若使用0-based则可删除此步）
        current_cycle = [x + 1 for x in current_cycle]
        cycles.append(current_cycle)
        
        # 移除环内所有参与者（转回0-based操作）
        for person in current_cycle:
            active.remove(person - 1)
    
    return cycles

# 示例：列表嵌套列表存储偏好（0-based索引对应原1-4号参与者）
preferences = [
    [1, 2, 3],   # 原1号的偏好：2, 3, 4
    [2, 0, 3],   # 原2号的偏好：3, 1, 4
    [1, 0, 3],   # 原3号的偏好：2, 1, 4
    [0, 1, 2]    # 原4号的偏好：1, 2, 3
]

cycles = find_and_remove_cycles(preferences)
print("Cycles found:", cycles)

代码说明 #

1. 活跃参与者管理：用active集合标记当前未被移除的参与者，避免修改原始偏好列表，逻辑更清晰。
2. 首选映射构建：每次迭代为每个活跃参与者找到当前可用的第一个偏好对象，构建完整的指向关系。
3. 环检测逻辑：通过追踪路径的方式识别环——沿着首选映射遍历，当遇到已在当前路径中的节点时，提取从该节点到路径末尾的部分作为环。
4. 编号转换：示例中默认将0-based索引转换为你原示例的1-based编号，若不需要可删除对应代码块。

运行上述代码，输出结果为Cycles found: [[2, 3], [1, 4]]，完全符合预期。

内容的提问来源于stack exchange，提问作者George