# lock_pairs skips final pair if it creates cycle

I have been working on the tideman problem from Problem Set 3. After multiple attempts, I have been able to pass all the required checks except one: "lock_pairs skips final pair if it creates cycle".

I realize that there are solutions available on the internet regarding this, but since I have tried to implement my custom form of a recursive solution, I would really appreciate some help on this.

Here's a snippet from the 'lock_pairs' and its helper, custom function that I have created:

``````// custom function for cycle checking
bool cycle_check(int from, int to)
{

int neighbours[candidate_count];

for (int i = 0; i < candidate_count; i++)
{
neighbours[i] = (int) locked[to][i]; // eg get all neighbours of A. (Wanting to check if we can establish pair from C to A)
}

if (neighbours[from] == 1) // if C exists in neighbours of A...
{
return true; //...then just return true. Since a path exists in reverse order already
}

int sum = 0;
for (int i = 0; i < candidate_count; i++)
{
sum += neighbours[i];
}
if (sum == 0) // if A has no neighbours...
{
return false; // ... then we can safely add this locked pair
}

else // else look for an indirect path from neighbours of A (for e.g)
{
for (int i = 0; i < candidate_count; i++)
{
if (neighbours[i] == 1) // if any other neighbour exists...
{
return false || cycle_check(from, to = i); //... then check for a possible path from that neighbour
}
}
}

return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
// to ascertain whether creating a locked_pair would creat a cycle or not...
// ... need to determine if a path already exists from (to to from)
// ... eg if want to see whether or not we can add a locked pair from C to A...
// ... need to see if a path from A to C already exists or not. If yes, then a cycle would be created. Hence we should not add.
void lock_pairs(void)
{
for (int i = 0; i < pair_count; i++)
{
int from = pairs[i].winner;
int to = pairs[i].loser;
locked[from][to] = true;

if (cycle_check(from, to)) // if path already exists...
{
locked[from][to] = false; //...set pair back to false
}
}

return;
}

``````

I have printed out the locked matrix at certain intervals including right at the end too. And despite it being seemingly correct, I am still unable to pass this check.

Any help on this would be highly appreciated, thanks.