CS50 Tideman问题：lock_pairs未跳过会产生环的最后一对

问题描述 #

我在完成CS50的Tideman作业时，遇到了lock_pairs函数的问题。check50测试显示，中间会产生环的配对能按预期跳过，但最后一对会产生环的配对无法跳过，导致对应测试失败。

相关代码 #

bool CycleCheckRecursion(int L, int W)
// Checks if there is a cycle. Returns 1 if cycle is found.
{
    for (int q = 0;  q <= pair_count - 1; q++)
    {
        if (locked[q][W] == true)
        {
            if (locked[L][q] == true)
            {
                return 1;
            }
            else
            {
                CycleCheckRecursion(L, q);
            }
        }
    }
    return 0;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{        // TODO
    for (int y = 0; y <= pair_count - 1; y++)
    {
        if (!CycleCheckRecursion(pairs[y].loser, pairs[y].winner))
        {
            locked[pairs[y].winner][pairs[y].loser] = true;
        }
    }
}

check50测试结果 #

:) tideman.c exists
:) tideman compiles
:) vote returns true when given name of candidate
:) vote returns false when given name of invalid candidate
:) vote correctly sets rank for first preference
:) vote correctly sets preferences for all voters
:) record_preferences correctly sets preferences for first voter
:) record_preferences correctly sets preferences for all voters
:) add_pairs generates correct pair count when no ties
:) add_pairs generates correct pair count when ties exist
:) add_pairs fills pairs array with winning pairs
:) add_pairs does not fill pairs array with losing pairs
:) sort_pairs sorts pairs of candidates by margin of victory
:) lock_pairs locks all pairs when no cycles
:( lock_pairs skips final pair if it creates cycle
    lock_pairs did not correctly lock all non-cyclical pairs
:) lock_pairs skips middle pair if it creates a cycle

问题分析 #

问题出在CycleCheckRecursion函数的递归调用处理上：当递归调用CycleCheckRecursion(L, q)找到环时，当前函数并没有把这个结果返回，而是继续执行后续循环，最后返回0。这会导致程序误判为没有环，从而错误地锁定了本应跳过的最后一对。

修复方案 #

修改CycleCheckRecursion函数中递归调用的逻辑，一旦递归返回true（找到环），就立刻向上返回true，不再继续循环：

bool CycleCheckRecursion(int L, int W)
// Checks if there is a cycle. Returns 1 if cycle is found.
{
    for (int q = 0;  q <= pair_count - 1; q++)
    {
        if (locked[q][W] == true)
        {
            if (locked[L][q] == true)
            {
                return 1;
            }
            else
            {
                // 若递归找到环，直接返回结果
                if (CycleCheckRecursion(L, q))
                {
                    return 1;
                }
            }
        }
    }
    return 0;
}

这样修改后，递归过程中只要发现环，就会逐层返回true，确保lock_pairs函数能正确判断是否应该跳过当前配对。

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