Please help about tideman lock_pair function!

Question

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

Check50 results:

:) lock_pairs locks all pairs when no cycles

:( lock_pairs skips final pair if it creates cycle

lock_pairs did not correctly lock all non-cyclical pairs

:( lock_pairs skips middle pair if it creates a cycle

lock_pairs did not correctly lock all non-cyclical pairs

I don't know where my logic is wrong. Hope you can point out. Thank you so much!

Answer 1

Maybe I'm just stating the obvious but you are not checking whether "locking in" an edge creates a cycle. As soon as you enter the first loop you are immediately setting the edge locked[pairs[i].winner][pairs[i].loser] to true. This is a problem because the Tideman algorithm specifically states that you should only set an edge to true if doing so will not create a cycle.

I'm also working on this function now and trying to figure out the code logic to determine whether locking in an edge will create a cycle. I understand it conceptually but having trouble translating it into code.