# Pset3 Tideman: lock_pairs skips middle pair if it creates a cycle

I'm having issues figuring out how to solve this problem without using recursion (I'm not sure how to solve things recursively). Its a program that determines the winner of a Tideman election and I'm getting the "skips middle pair" error. I've adjusted my approach multiple times and have come up with this idea:

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{

//Going through each pair and determining if it can be locked.
for (int i = 0; i < pair_count; i++)
{
locked[pairs[i].winner][pairs[i].loser] = true;

if (canilock(candidate_count))
{
locked[pairs[i].winner][pairs[i].loser] = false;
}
}

return;
}

bool canilock(int k)
{

//creating an int r that I will increment every time there is a unique locked winner
//creating an array of bools that is true when candidate k is a winner at least once

int r = 0;
bool edge[k];
for (int i = 0; i < k; i++)
{
edge[i] = false;
}

for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++)
{
if (locked[i][j] == true)
{
edge[i] = true;
}

}
}

for (int i = 0; i < k; i++)
{
if (edge[i] == true)
{
r++;
}
}

//if the number of unique winners is equal to the number of candidates then there is a loop by definition
if (r == k)
{
return true;
}

return false;

}

Not sure why this would skip middle pair. Does this problem want the program to work such that there is never a loop even if the loop doesn't change the winner? For instance, if there are 5 candidates and 3 of them are somehow in a loop, but the source/winner is not. Does the problem call for even the submatrix to be unlooped? If so, how do I do that?

• I've changed my approach to remove any assumption and I'm still getting the "skips middle pair" error. – timmy a May 26 '20 at 16:43