CS50 PSET3 Tideman：lock_pairs函数无法通过check50测试求助

Hey there! No need to apologize—we’ve all been stuck on CS50’s Tideman problems, especially when it comes to handling cycles. Let’s break down what’s off with your current implementation and get it working properly.

What’s Wrong with Your Current Code? #

Your approach using win_count doesn’t address the core requirement of the lock_pairs function: we need to check if adding each pair will create a cycle in the directed graph before locking it. Right now, you’re locking all pairs first and then trying to adjust based on win counts, which doesn’t correctly detect or prevent cycles. That’s why you’re failing the two cycle-related check50 tests.

Correct Approach #

The Tideman algorithm requires us to:

• Iterate through each pair in order of decreasing strength (which the pairs array already is)
• For each pair, temporarily lock it
• Check if this temporary lock creates a cycle in the graph
  • If a cycle is created, don’t lock the pair (skip it)
  • If no cycle is created, keep the pair locked

To check for cycles, we’ll need a helper function that uses depth-first search (DFS) to see if we can traverse from the loser back to the winner of the current pair. If we can, adding the pair creates a cycle.

Fixed Code #

First, add this helper function (you can put it above lock_pairs in your code):

// Helper function to check if adding a pair (winner -> loser) creates a cycle
bool has_cycle(int start, int current) {
    // If we've looped back to the start, we have a cycle
    if (current == start) {
        return true;
    }
    // Check all nodes current points to
    for (int i = 0; i < candidate_count; i++) {
        if (locked[current][i]) {
            // Recursively check if we can get back to start from i
            if (has_cycle(start, i)) {
                return true;
            }
        }
    }
    // No cycle found
    return false;
}

Now, rewrite your lock_pairs function like this:

void lock_pairs(void) {
    // Iterate through all pairs in order of strength
    for (int i = 0; i < pair_count; i++) {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;
        
        // Temporarily lock the pair
        locked[winner][loser] = true;
        
        // Check if this creates a cycle (can we get from loser back to winner?)
        if (has_cycle(winner, loser)) {
            // Cycle detected, unlock the pair
            locked[winner][loser] = false;
        }
        // If no cycle, leave the pair locked
    }
    return;
}

How This Works #

1. Helper Function (has_cycle):
   • Takes a start node (the winner of the current pair) and a current node (the loser we’re checking from)
   • Uses DFS to traverse the directed graph: if we can reach the start node from current, that means adding the winner -> loser edge creates a cycle.
2. lock_pairs Function:
   • Goes through each pair one by one. For each, it first locks the pair.
   • It then uses the helper to check if locking this pair creates a cycle (by seeing if the loser can reach the winner).
   • If a cycle is found, it unlocks the pair (so we skip locking it). If not, the pair stays locked.

This implementation strictly follows the Tideman rules and will pass all check50 tests, including the ones where adding a middle or final pair would create a cycle.

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