0

My code fails at check50 but I can't understand why. It that seems my code actually finds cycles, but also produces false-positives (I guess).

check50 output for the lock_pairs function:

:( lock_pairs locks all pairs when no cycles
    lock_pairs did not lock all pairs
:) lock_pairs skips final pair if it creates cycle
:) lock_pairs skips middle pair if it creates a cycle

I tried to solve it simple. Here is the code for my lock_pairs function:

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // Iterate over all pairs
    for(int i = 0; i < pair_count; i++)
    {
        // Check if the winner of that pair is a loser in any locked pair
        bool cycle = false;
        for(int j = 0; j < candidate_count; j++)
        {
            if(locked[pairs[i].loser][pairs[j].winner])
            {
                cycle = true;
            }
        }

        // If the winner isn't a loser in any other pair, there will be no circle and we can lock the pair
        if(!cycle)
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
    return;
}
1

Being the loser of an already locked pair is not necessarily sufficient to create a cycle. If A beats B, and B beats C, there is no cycle, but your algorithm will not lock in B -> C if A -> B is already locked.

You must log in to answer this question.

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