CS50 Tideman算法中cycle函数递归逻辑疑问

你提到的cycle函数代码如下：

// Test for cycle by checking arrow coming into each candidate
bool cycle(int end, int cycle_start)
{
    // Return true if there is a cycle created (Recursion base case)
    if (end == cycle_start)
    {
        return true;
    }
    // Loop through candidates (Recursive case)
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[end][i])
        {
            if (cycle(i, cycle_start))
            {
                return true;
            }
        }
    }
    return false;
}

你的理解确实有误。locked数组初始值全为false没错，但这个cycle函数并非在数组初始化后立刻调用，而是在Tideman算法的执行过程中，每次尝试锁定一条新边（即把locked[胜者][败者]设为true）之前被调用的。此时locked数组已经有部分元素被设为true，所以if (locked[end][i])的条件是会被触发的。

这个递归函数的工作原理 #

Tideman算法的核心规则是：按对决的优势从大到小排序所有候选人之间的胜负关系，然后依次锁定胜者指向败者的箭头，但绝对不能形成循环——一旦锁定某条边会导致循环，就跳过这条边。这个cycle函数就是用来检查「锁定当前边是否会形成循环」的工具。

函数的逻辑拆解：

• 参数含义：end是当前追踪的候选人节点，cycle_start是我们要验证是否能绕回的起点（也就是准备锁定的新边的胜者）。当准备锁定边winner→loser时，会调用cycle(loser, winner)，检查从loser出发能否最终走到winner——如果能，说明加上这条边就会形成winner→loser→...→winner的循环。
• 基例：如果end == cycle_start，说明找到了一条从起点出发又回到起点的路径，即循环存在，返回true。
• 递归逻辑：遍历所有候选人i，如果locked[end][i]为true，意味着存在一条从end指向i的已锁定箭头，我们就继续递归追踪i这个节点，看能否最终回到cycle_start。
• 无循环情况：如果遍历完所有可能的路径都没回到起点，返回false，说明锁定当前边不会形成循环，可以安全锁定。

实际调用场景示例 #

假设已经锁定了两条边：locked[B][C] = true（B胜C）、locked[C][A] = true（C胜A），现在要尝试锁定locked[A][B] = true（A胜B）：

1. 调用cycle(B, A)，检查从B出发能否走到A
2. 初始end为B，不等于cycle_start（A），遍历所有候选人，发现locked[B][C]为true，调用cycle(C, A)
3. end为C，不等于A，遍历候选人，发现locked[C][A]为true，调用cycle(A, A)
4. 触发基例，返回true，说明循环存在，因此跳过锁定A→B这条边

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