I'm working on the CS50x's Tideman problem

(https://cs50.harvard.edu/x/2022/psets/3/tideman/).

All the tests passed except one:

:( lock_pairs skips final pair if it creates cycle lock_pairs did not correctly lock all non-cyclical pairs

I guess the problem is in my custom function has_circle that checks if there will be a circle in a graph if an edge is placed.

I would really be grateful for your help. I wrote the rest of the code fairly quickly (for a begginer) but this bug is just....

This is the code:

bool has_circle(int loser, int winner)
{
    // base case, break
    if (winner == loser)
    {
        return true;
    }

    // iterate through all pairs to see if our loser is a winner against someone
    for (int i = 0; i < pair_count; i  )
    {
        if (locked[loser][i] == true)
        {
            // check if primary winner is a loser against i, if edge can be placed
            return has_circle(i, winner);
        }
    }
    return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    //
    for (int i = 0; i < pair_count; i  )
    {
        // check for circle
        if (!has_circle(pairs[i].loser, pairs[i].winner))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
    return;
}

CodePudding user response：

This line

return has_circle(i, winner);

always returns a value, ending the the loop and the recursion, the first time locked[loser][i] is true, regardless of the actual result of has_circle.

Instead, you want the loop to be able to continue if has_circle returns false, but break the loop and return true when has_circle returns true.

bool has_circle(int loser, int winner)
{
    // base case, break
    if (winner == loser)
    {
        return true;
    }

    // iterate through all pairs to see if our loser is a winner against someone
    for (int i = 0; i < pair_count; i  )
    {
        if (locked[loser][i] && has_circle(i, winner))
        {
            return true;
        }
    }

    return false;
}