CS50 Tideman：lock_pairs函数循环检测逻辑问题咨询

我在CS50的Tideman项目中，为lock_pairs函数调试了好几天，自认为逻辑没问题，但check50唯独在“lock_pairs skips final pair if it creates cycle”测试项上失败。找到一份递归实现的lock_pairs代码后，所有测试都通过了，却搞不懂两者的差异。我试过用debug50和绘图分析，还是没找到关键区别，希望有人分步解释这份递归函数为什么正确，以及我的代码哪里出了问题。

正确的递归实现代码 #

// 递归函数：检查添加当前配对是否会形成环
bool makes_circle(int cycle_start, int loser)
{
    if (loser == cycle_start)
    {
        // 当前遍历到的节点等于环的起点，说明形成了环
        return true;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[loser][i])
        {
            if (makes_circle(cycle_start, i))
            {
                // 沿着锁定的边继续遍历，找到环则返回true
                return true;
            }
        }
    }
    return false;
}

// 按顺序锁定配对，确保不形成环
void lock_pairs()
{
    for (int i = 0; i < pair_count; i++)
    {
        if (!makes_circle(pairs[i].winner, pairs[i].loser))
        {
            // 只有当添加该配对不会形成环时，才锁定它
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
}

递归代码的正确性分析 #

• 核心逻辑：深度遍历检测环
  当要锁定(winner, loser)配对时，核心问题是：从loser出发，沿着已锁定的胜负边，能不能走到winner？如果能，就会形成winner → loser → ... → winner的环，不能锁定；反之则可以锁定。
  递归函数makes_circle就是做这件事：以当前配对的winner为目标起点，从loser开始深度优先遍历所有已锁定的边，只要找到一条路径回到起点，就判定会形成环。
• 覆盖所有环结构
  递归会沿着每一条边不断深入，不管路径长度是2、3还是更长。比如存在loser → A → B → ... → winner的长路径时，递归会一步步遍历到A、B直到找到起点，不会漏掉任何可能的环。

我的代码实现 #

void lock_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        bool cycle = false;
        // 检查当前配对的loser是否击败过其他候选人
        for (int j = 0; j < candidate_count && !cycle; j++)
        {
            if (locked[pairs[i].loser][j])
            {
                // 如果loser击败了j，检查j是否击败了当前配对的winner
                for (int k = 0; k < candidate_count && !cycle; k++)
                {
                    if (locked[j][k])
                    {
                        if (k == pairs[i].winner)
                        {
                            cycle = true;
                        }
                    }
                }
            }
        }
        if (!cycle)
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
    return;
}

我的代码的问题所在 #

你的代码只检测了长度为3的环（winner → loser → j → winner），完全忽略了更长的环结构：

• 比如存在winner → loser → A → B → winner这样的环时，你的代码只会检查loser直接指向的j，然后看j是否直接指向winner，不会继续遍历A、B的后续路径。
• 当测试项要求跳过会形成环的最后一个配对时，大概率是出现了长度大于3的环，你的代码没检测出来，错误地锁定了配对，导致环形成，所以测试失败。

举个具体例子：
假设候选人是W（当前配对的winner）、L（loser）、A、B，已锁定的边是L→A、A→B、B→W。现在要添加W→L，你的代码只会检查L指向的A，发现A不直接指向W，就判定没有环，错误锁定了W→L；但递归代码会从L出发，遍历到A、B，最后到W，发现等于起点，判定有环，不会锁定这条边。

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