How do I implement lock_pair function correctly in Tideman?

Question

Can anyone help check what is wrong with my logic? I tried implementing lock_pairs using these lines of codes:

void lock_pairs(void)
{
    // TODO
    int count = 0;

    for (int i = 0; i < pair_count; i++)
    {
        for (int j = i; j < pair_count; j++)
        {
            if(pairs[i].winner == pairs[j].loser)
            {
                count++;
            }
        }

        if (count == 0)
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }

        else
        {
            locked[pairs[i].winner][pairs[i].loser] = false;
        }
    }

    return;
}

My logic is that the program will check whether a winner in any pairs has been a loser or not. If he/she has, then it will increment count by 1, noticing a cycle. If count has been changed, then pairs would not be locked to avoid the cycle. Else if count == 0, then the pairs are suitable to be locked.

This is what check50 returned:

:) 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

Any help is appreciated.

Answer 1

pair[i].winner may be equal to pair[j].loser in many cases where pair[i].winner is not the end element in the chain. Consider voting of three candidates A, B, C where sorted pairs as follows: 1. B->C, 2. A->B. Here, first pair meets your condition for incrementing the value of count but there looks no harm in assigning true to this combination.

Hint: Consider an example of 4-5 candidates, shape a cyclic graph and write down your pairs matrix. Now in order to avoid this cycle, mark the values in the locked matrix as true/false. You may be required to navigate recursively through the locked matrix to avoid cyclic graph.

I hope it gives you some idea to proceed with the issue.