CS50 Tideman问题：lock_pairs函数未锁定所有无环配对

问题描述 #

完成CS50 2023年Tideman问题集时，其余函数运行正常，但lock_pairs函数不符合要求：check50提示“lock_pairs locks all pairs when no cycles，Cause: lock_pairs did not lock all pairs”。当前实现通过两层循环检查环的逻辑错误，无法正确锁定所有无环的配对，且要求不新增iscycle类辅助函数。

原代码问题分析 #

原lock_pairs函数的内层循环逻辑完全偏离了环检测的核心：它遍历所有pair检查locked[pairs[i].loser][pairs[j].winner]，这种方式只能检测单一反向边，无法判断是否存在从loser到winner的完整路径，导致大量应该锁定的配对被错误设为false，同时可能误锁会形成环的配对。

修复后的lock_pairs函数 #

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;
        bool cycle = false;

        // 初始化访问标记数组，记录是否已遍历该候选人
        bool visited[MAX] = {false};
        // 从loser开始遍历，检查能否走到winner
        int current = loser;
        // 用循环模拟路径遍历（避免递归，不新增函数）
        while (true)
        {
            visited[current] = true;
            bool found_next = false;
            // 遍历所有候选人，寻找当前节点能到达的下一个节点
            for (int j = 0; j < candidate_count; j++)
            {
                if (locked[current][j] && !visited[j])
                {
                    // 如果走到了winner，说明会形成环
                    if (j == winner)
                    {
                        cycle = true;
                        break;
                    }
                    current = j;
                    found_next = true;
                    break;
                }
            }
            if (cycle || !found_next)
            {
                break;
            }
        }

        // 没有环则锁定当前配对
        if (!cycle)
        {
            locked[winner][loser] = true;
        }
    }

    // 可选：自我检查输出
    for(int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            printf("%i ", locked[i][j]);
        }
        printf("\n");
    }
    return;
}

修复逻辑说明 #

• 按顺序处理配对：保持原逻辑，按排序后的优先级（胜利强度从高到低）处理每个配对
• 环检测核心：对于当前配对的winner和loser，从loser出发遍历已锁定的边：
  • 用visited数组避免重复遍历同一个候选人
  • 每次寻找当前节点可到达的下一个节点（通过已锁定的locked[current][j]）
  • 如果遍历过程中到达winner，说明添加当前边会形成环，跳过锁定
• 无环则锁定：确认不会形成环后，将locked[winner][loser]设为true

这个实现完全在lock_pairs函数内部完成环检测，没有新增任何辅助函数，同时正确处理了所有无环配对的锁定，解决了check50的报错问题。

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