Ретроанализ и ничьи

Пусть фишка стоит в вершине ориентированного графа, ход — перейти по ребру, проигрывает тот, кто не может сходить. Если в графе есть циклы, рекурсия из предыдущей статьи зациклится, а у игры появляется третий исход: партия может продолжаться бесконечно, и это ничья.

Ничья — не «никто не выиграл по договорённости». Это значит: у проигрывающей стороны есть способ вечно уклоняться, а у выигрывающей нет способа её дожать.

Идея: считать назад

Достоверно известен исход только у вершин без исходящих рёбер: там ходить некому, значит позиция проигрышная. От них и пойдём назад по рёбрам.

Держим для каждой вершины счётчик left — сколько её ходов ещё не привели в выигрышную позицию. Изначально это исходящая степень.

• Если из $u$ есть ребро в проигрышную $v$ — вершина $u$ выигрышная, сразу.
• Если ребро ведёт в выигрышную $v$ — уменьшаем left[u]; когда счётчик дошёл до нуля, все ходы из $u$ ведут в выигрышные, и $u$ проигрышная.
• Вершины, до которых очередь так и не дошла, — ничейные.

std::vector<int> back[N];      // рёбра в обратную сторону
std::vector<int> left(n + 1);  // исходящие степени
std::vector<char> state(n + 1, DRAW);

std::queue<int> q;
for (int v = 1; v <= n; v++) if (left[v] == 0) state[v] = LOSE, q.push(v);
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int u : back[v]) {
        if (state[u] != DRAW) continue;
        if (state[v] == LOSE) { state[u] = WIN; q.push(u); }
        else if (--left[u] == 0) { state[u] = LOSE; q.push(u); }
    }
}

Каждая вершина попадает в очередь не больше одного раза, каждое обратное ребро просматривается один раз: $O(V + E)$.

Почему ничьи получаются правильно

Вершина объявляется выигрышной, только когда найден конкретный ход в проигрышную, и проигрышной — только когда все её ходы разобраны. Значит для каждой такой вершины исход подтверждён конечной цепочкой рассуждений, то есть партия из неё кончается за конечное число ходов.

Оставшиеся вершины ни разу не получили подтверждения. Из каждой из них есть ход в другую неподтверждённую (иначе счётчик дошёл бы до нуля) — и по этим ходам можно ходить вечно. Это и есть ничья.

Петли и кратные рёбра

Условия часто разрешают петли и кратные рёбра, и оба случая ломают неаккуратный код.

Петля даёт вершине ход в саму себя — а значит, возможность тянуть время. Специально обрабатывать её не нужно: счётчик просто никогда не дойдёт до нуля, и вершина честно окажется ничейной или выигрышной.

Кратные рёбра нельзя схлопывать: left считает рёбра, а не соседей. Если ребро $u \to v$ записано дважды, то и уменьшать счётчик придётся дважды, иначе он до нуля не дойдёт.

Смежное

• Выигрышные и проигрышные позиции — ациклический случай;
• Обход в ширину — тот же каркас очереди.