0

Here's my code for lock pairs-

bool check_cycle(int start, int end)
{
    if (end == start)
    {
        return false;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[end][i])
        {
            if (check_cycle(i, start))
            {
                return false;
            }

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

Here's what I'm trying to do. When check_cycle function is called, start is winner & end is looser. I will check whether start equals end(recursive case), if it is equal then I return false. Now if they aren't equal then I loop through all the candidates & check whether locked[end][i] is true as I'm making end as winner & checking if there's any pair with end as winner which is already locked. If it is true, then I check whether there's a cycle or not. so I call check_cycle function again & check whether check_cycle(i,start) is true or not. If it is false then there's a cycle & that particular pair won't be locked.

I'm getting this when I run check50-

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

Can someone tell me where my code is wrong?

1
  • Your check_cycle function returns true if there is no cycle and false if there is, right? – Robert S. Pratt Mar 3 at 21:18

You must log in to answer this question.

Browse other questions tagged .