CS50 Tideman：lock_pairs函数因循环判定错误跳过最后一对求助

你的代码核心问题出在creates_cycle函数的递归调用逻辑上，另外循环检测的覆盖范围也存在漏洞，具体问题和修复方案如下：

1. 递归调用未传递返回结果 #

你在递归调用creates_cycle(n, original_winner, temp_win_los)时，仅执行了函数但未返回其结果。这会导致即使递归过程中发现了循环，上层函数也无法感知，最终仍会返回false，错误地允许循环产生。

2. 循环检测逻辑不完整 #

当前的creates_cycle仅遍历前n条已锁定边，没有完整追踪从temp_win_los出发的所有路径。比如多步跳转的循环（A→B，B→C，C→A），现有逻辑无法检测到这类情况。

修正后的代码 #

修正creates_cycle函数 #

改用深度优先搜索（DFS）完整追踪路径，确保检测所有可能的循环：

bool creates_cycle(int start, int target) {
    // 当前节点等于目标，说明找到循环
    if (start == target) {
        return true;
    }

    // 遍历所有节点，检查是否有从start指向其他节点的锁定边
    for (int i = 0; i < candidate_count; i++) {
        if (locked[start][i]) {
            // 递归检查从i出发能否回到target
            if (creates_cycle(i, target)) {
                return true;
            }
        }
    }

    return false;
}

修正lock_pairs函数 #

简化逻辑并调用修正后的循环检测函数：

void lock_pairs(void) {
    for (int i = 0; i < pair_count; i++) {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;

        // 检查锁定当前边后是否形成循环：从loser出发能否回到winner
        if (!creates_cycle(loser, winner)) {
            locked[winner][loser] = true;
        }
    }
}

说明 #

• 修正后的creates_cycle从loser节点出发，递归遍历所有已锁定边，若能回到winner则判定为循环。
• 去掉了原代码中i<1的特殊判断，因为新逻辑对第一条边同样适用（第一条边不可能形成循环，检测结果自然为false，会正常锁定）。

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