CS50 Tideman中lock_pairs函数调试：无法跳过形成环的最终配对

错误提示 #

:( Lock pairs skips final pair if it creates cycle.

现有代码实现 #

void add_pairs(void)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            if (preferences[i][j] < preferences[j][i])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
            else if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
        }
    }
    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    int swap_counter = -1;
    // iterate through pairs array, which is an array of struct (winner/loser)
    for (int i = 0; i < pair_count; i++)
    {
        swap_counter = 0;
        // Compares first pair found to second pair found in pairs array. If first pair is smaller victory, swaps.
        int pair_a = preferences[pairs[i].winner][pairs[i].loser];
        int pair_b = preferences[pairs[i+1].winner][pairs[i+1].loser];
        if (pair_a < pair_b)
        {
            // Create variable to temporarily hold values of switched pair
            pair tempswitch;
            tempswitch.winner = pairs[i].winner;
            tempswitch.loser = pairs[i].loser;
            // In case of first pair being smaller than second pair, swap.
            pairs[i].winner = pairs[i+1].winner;
            pairs[i].loser = pairs[i+1].loser;
            pairs[i+1].winner = tempswitch.winner;
            pairs[i+1].loser = tempswitch.loser;
            swap_counter++;
        }
    }
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // Create loop to use as starting point for circle detection
    for (int i = 0; i < pair_count; i++)
    {
        // Initialize temp variable as the loser of the starting point
        int temp_variable = pairs[i].loser;
        // initialize loopdetect and hitcount
        int infLoopDetector = 0;
        int hit_count = 0;
        while (infLoopDetector < pair_count)
        {
            // While loop has 2 exit conditions:
            // Exit 1: # of loops exceeds the number of actual pairs. Circle present in the code -- exit while loop and report i as troublemaker
            // Exit 2: Dead end in which an unequivocal loser was found (no winning relationships). No hits after running j loop = exit
            // if pair is locked, can iterate through it
            // if pair is not locked, don't iterate through it
            hit_count = 0;
            for (int j = 0; j < pair_count; j++)
            {
                if (locked[pairs[j].winner][pairs[j].loser] == true || j == i)
                {
                    if (temp_variable == pairs[j].winner)
                    {
                        temp_variable = pairs[j].loser;
                        hit_count++;
                        infLoopDetector++;
                        break;
                    }
                }
            }
            if (hit_count == 0 && infLoopDetector < pair_count)
            {
                locked[pairs[i].winner][pairs[i].loser] = true;
                break;
            }
        }
        if (infLoopDetector == pair_count)
        {
            locked[pairs[i].winner][pairs[i].loser] = false;
        }
    }
}

问题分析 #

1. sort_pairs函数排序不完整 #

当前排序逻辑仅遍历数组一次，属于不完整的冒泡排序，无法保证所有配对按胜利强度降序排列。排序错误会导致lock_pairs的处理顺序混乱，直接影响环检测结果。

2. lock_pairs的环检测逻辑存在缺陷 #

• 错误纳入未锁定配对：代码中j == i的条件会把当前待检测的未锁定配对当作已存在的边遍历，导致环的误判。
• 终止条件不合理：用pair_count作为循环上限，而环的最大长度是候选人数candidate_count（环是候选人间的循环，与配对数无关），这会导致检测逻辑提前终止或进入无效循环。
• 检测方向错误：正确的环检测应判断：添加winner→loser的边后，是否存在从loser到winner的路径。若存在则形成环，不能锁定；反之则可以锁定。

修复方案 #

第一步：修复sort_pairs函数 #

使用完整的冒泡排序，确保配对严格按胜利强度降序排列：

void sort_pairs(void)
{
    int swapped;
    do {
        swapped = 0;
        for (int i = 0; i < pair_count - 1; i++)
        {
            int strength_a = preferences[pairs[i].winner][pairs[i].loser];
            int strength_b = preferences[pairs[i+1].winner][pairs[i+1].loser];
            if (strength_a < strength_b)
            {
                // Swap the pairs
                pair temp = pairs[i];
                pairs[i] = pairs[i+1];
                pairs[i+1] = temp;
                swapped = 1;
            }
        }
    } while (swapped);
}

第二步：重写lock_pairs的环检测逻辑 #

新增路径检测辅助函数，精准判断环是否会形成：

// 辅助函数：检测从start到end是否存在已锁定的路径
bool has_path(int start, int end)
{
    if (start == end)
    {
        return true;
    }
    // 遍历所有已锁定的边
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[start][i] == true && has_path(i, end))
        {
            return true;
        }
    }
    return false;
}

void lock_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;
        // 若添加当前边后，loser无法到达winner，则不会形成环，可锁定
        if (!has_path(loser, winner))
        {
            locked[winner][loser] = true;
        }
        // 否则跳过该配对，不锁定
    }
}

修复说明 #

1. sort_pairs修复：完整的冒泡排序会持续遍历数组直到无交换发生，确保配对按胜利强度从高到低严格排序。
2. lock_pairs修复：
   • has_path函数通过递归遍历已锁定的边，精准判断两个候选人之间是否存在路径。
   • 仅当添加当前边不会形成环时才锁定，彻底解决最后一个配对的环检测问题。

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