Принцип слияния

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

Формулировка

Принцип слияния. Вершины, лежащие на одном цикле, можно склеить в одну; рёбра цикла превращаются при этом в петли при склеенной вершине. Значение игры не меняется.

Петля — это ребро, которое стирается, ничего не отрывая, то есть игра ценности $1$: один ход и всё. Значит, цикл длины $L$ равносилен $L$ петлям, а их суммарное значение —

$$\underbrace{1 \oplus 1 \oplus \cdots \oplus 1}_{L} = L \bmod 2.$$

Треугольник равносилен одному ребру. Квадрат равносилен пустоте. Это самая полезная форма правила: длина цикла не важна, важна её чётность.

Как считать

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

$$g(K) = \bigl(E_K \bmod 2\bigr) \ \oplus \bigoplus_{L \text{ — сын } K} \bigl(g(L) + 1\bigr),$$

где $E_K$ — количество рёбер внутри компоненты $K$ (петли и кратные рёбра считаются).

Порядок работы:

1. найти мосты обходом в глубину;
2. сжать компоненты рёберной двусвязности;
3. подвесить дерево мостов за компоненту с землёй;
4. посчитать значение снизу вверх.

Всё вместе — $O(n + m)$.

Мелочи, на которых спотыкаются

• Петля во входных данных — это цикл длины $1$, то есть готовое ребро внутри компоненты. Отдельного разбора не требует, но и выбрасывать её нельзя.
• Кратные рёбра — цикл длины $2$, то есть чётность. Два параллельных ребра между вершинами вместе дают ноль, а не два.
• Отдельные компоненты связности, не соединённые с землёй, в игре не участвуют вовсе: они уже отвалились.
• Мосты искать без рекурсии — по той же причине, что и всё остальное на больших графах.

Смежное: Гранди на деревьях, сумма игр.