CS50 Pset3 Tideman算法lock_pairs函数报错原因排查

云原生阿岚

2026-8-28

问题描述

完成了CS50课程Tideman选举算法项目中lock_pairs函数的实现，自行构造的测试用例运行均符合预期，但提交至评测系统时返回两个报错：

:( 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
lock_pairs did not correctly lock all non-cyclical pairs

已完成本次作业提交，不介意扣除对应分数，仅希望明确代码存在的逻辑错误。
对应实现代码如下：

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // initialising an array with all the untargted candidates (no arrows pointing to them)
    bool untargeted[candidate_count];
    // initialising a variable to keep track of how many sources (untargted candidates)
    int untar = 0;

    // chacking all as untargeted
    for (int i = 0; i < candidate_count; i++)
    {
        untargeted[i] = true;
        untar++;
    }

    // iterating over all pairs
    for (int i = 0; i < pair_count; i++)
    {
        // checking if the loser is the only untargeted candidate to prevent cycles
        if (!(untargeted[pairs[i].loser] && untar == 1))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
            // checking if loser was untargted to mark them as a targeted
            if (untargeted[pairs[i].loser])
            {
                untar--;
                untargeted[pairs[i].loser] = false;
            }
        }
    }
    return;
}

代码逻辑错误说明

你的环判断逻辑从原理上就不成立，靠「待加边的输家是不是当前仅剩的无入度节点」来判断会不会成环，完全搞错了有向图成环的判定规则。

首先你要明确：「有向无环图至少存在一个入度为0的源节点」只是必要不充分条件，反过来图里有源节点，不代表图里没有环。举个很简单的4候选场景：候选人A、B、C、D，按胜负强度排序的边为A胜B、B胜C、C胜A、A胜D。按你的代码逻辑执行：
1. 初始化所有节点为无入度状态，untar=4
2. 加A→B边：B从无入度变为有入度，untar降到3
3. 加B→C边：C从无入度变为有入度，untar降到2
4. 处理C→A这条边时，无入度节点是A和D，untar=2，你的判断条件untargeted[pairs[i].loser] && untar == 1不成立，会直接加上C→A边，直接形成A→B→C→A的环。这时候整张图还有D这个无入度节点，你的逻辑会判定加边合法，但实际上环已经出现了，这就是你过不了「中间边成环需要跳过」测试用例的核心原因。
其次你的成环场景覆盖极窄，只有当加边会把最后一个源节点连入、导致整张图没有源的时候才能拦住，但凡环出现在加边过程的中间步骤、且图里还有其他未被连入的源节点，你的逻辑完全识别不出来。
最后你没搞对lock_pairs成环判定的核心逻辑：当你要加winner指向loser的边时，只需要检查当前已经锁定的边构成的图中，能不能从loser出发，沿着已有的单向边一路走到winner。如果能走到，加这条边就会形成闭环，必须跳过；如果走不到，加边就不会产生环，可以直接锁定。这个判断和当前有多少个入度为0的节点、当前输家是不是入度为0的节点没有必然联系：哪怕输家有入度，只要从它出发走不到赢家，加边就合法；哪怕输家是入度为0的节点，只要从它出发能走到赢家，加边一样会成环。

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