Блог

Не удалось выяснить тестовый случай, в котором этот код не работает. Все зеленые, за исключением этой ошибки: CS50 — pset3-tideman: lock_pairs неправильно заблокировал все нециклические пары. Мне нужно знать логический изъян здесь, больше, чем решение.

// Блокируйте пары в графе кандидатов по порядку, не создавая циклов

 void lock_pairs(void)
{
    // TODO
    for (int i = 0; i < pair_count; i   )
    {
        if(!is_circle(pairs[i].loser, pairs[i].winner))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }

    }
    return;
}

bool is_circle(int loser, int winner)
{
    if (loser == winner)
    {
        return true;
    }
    for (int i = 0; i < pair_count; i   )
    {
        if (locked[loser][i])
        {
            return is_circle(i, winner);
        }
    }
    return false;
}
 

Если рекурсивный вызов is_circle возвращает false , функция может вернуться не сразу, но должна проверить возможные другие ребра пары из локального i :

             return is_circle(i, winner);
 

должно быть

             if (is_circle(i, winner)) return true;