CS50 PSET3 Tideman：lock_pairs自测正常但check50测试失败求助

问题背景 #

自行完成单元测试后结果正常，但check50返回错误：

:( lock_pairs locks all pairs when no cycles
    lock_pairs did not lock all pairs
:) lock_pairs skips final pair if it creates cycle
:( lock_pairs skips middle pair if it creates a cycle
    lock_pairs did not correctly lock all non-cyclical pairs

lock_pairs函数要求：The function should create the locked graph, adding all edges in decreasing order of victory strength so long as the edge would not create a cycle.

我的实现代码 #

lock_pairs函数 #

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

        if (check_cycle_winner(winner, loser, i) && check_cycle_loser(loser, winner, i))
        {
            locked[winner][loser] = false;
        }
        else
        {
            locked[winner][loser] = true;
        }
    }
    return;
}

辅助函数 #

bool check_cycle_winner(int winner, int loser, int index)
{
    if (winner == loser) return true;

    if (index == 0) return false;

    return check_cycle_winner(winner, pairs[index - 1].loser, index -1);
}

bool check_cycle_loser(int loser, int winner, int index)
{
    if (loser == winner) return true;

    if (index == 0) return false;

    return check_cycle_loser(loser, pairs[index - 1].winner, index -1);
}

引导思考问题 #

• 判断添加winner→loser这条边是否会形成环，核心应该检查什么？是不是要确认从loser出发，能否通过已锁定的边走到winner？
• 你的辅助函数是遍历pairs数组的前index项，而不是遍历已经被锁定的边，这是否符合当前图的实际状态？毕竟有些前面的pair可能因为会形成环而没被锁定，不能默认它们都在图里。
• 第一个测试用例要求无环时锁定所有pair，你的代码为什么没做到？是不是你的判断条件错误地将某些不会形成环的边判定为会形成环？
• 当处理第一个pair（index=0）时，你的辅助函数直接返回false，结合lock_pairs的判断逻辑，这条边会被正确锁定吗？
• 假设现在已经锁定了一些边，当处理下一个pair时，你应该基于哪些边来判断环的存在？是已锁定的边，还是pairs里之前的所有项？

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