1

I am unable to pass the above-mentioned check. I can't see the issue. I would greatly appreciate if someone can share some insights. Code is below:

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

// Check for cycle in the graph
// l represents loser and w represents winner
bool check_cycle(int l, int w)
{
    if (locked[l][w] == true)
    {
        return true;
    }

    for (int j = 0; j < candidate_count; j++)
    {
        if (j != l && locked[l][j] == true && j != w)
        {
            return check_cycle(j, w);
        }
    }

    return false;
}

I tried comparing some test cases with tideman.netlify.app and our locked matrix are identical from my testings. Any comment on my coding style is also greatly appreciated, I am still learning to code efficiently!

1 Answer 1

3

The problem likely originates in your second for loop, where you return check_cycle(j, w) if the condition is true (meaning that there is an edge from the loser to another candidate), and you proceed to the next node (=j) of the graph.

I'm not going to reveal the full solution to you because of the academic honesty guidelines that are applied to CS50, but here are some thoughts on how to approach the solution. I suggest you start with the first thought and only proceed to the next item if your problem remains unsolved (the hints get more & more obvious the further you read).

  • What happens if there are multiple "branches" from a node? i.e. if there are multiple arrows pointing to the loser candidate - or worded differently, multiple values of j for which locked[l][j] is true.
  • Does your for loop really iterate through all these branches or maybe just one of them?
  • Remember that a return statement effectively stops/exits the for loop (same as writing break;)
  • How can you evaluate the response from your recursive call to check_cycle without breaking the for loop?
  • You only want to reach the return statement if the branched path ends in a cycle, because then all other cases don't matter anymore. If a branch does not lead back to the winner (=no cycle), you probably don't want to already exit from your for loop, because there might be other branches that create a cycle.

Another comment (just style-related, doesn't affect the output): You don't need to check for j!=w in the last if condition, because that is already handled by the first if statement in check_cycle, which is always checked before the for loop starts.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .