Странная игра на графе

Для начала заметим, что у графа может быть несколько компонет связности. При этом первый игрок, первым ходом выбирая ребро, фиксирует ее. Значит можно рассматривать компоненты связности независимо друг от друга.

Теперь рассмотрим, какая компонента связности будет выигрышной. Можно доказать, что если в компоненте связности нечетное число ребер, первый игрок может выиграть. Для этого, сделаем лемму: В любом связном графе, содержащем нечетное число ребер, для любой вершины можно выбрать смежное с ней ребро, что после его удаления, во всех получившихся компонентах связности (одной или двух), число ребер будет четно. Назовем такое ребро хорошим.

Тогда, первому игроку нужно будет играть следующим образом:

  1. Выбрать компоненту с нечетным числом ребер
  2. Выбрать в этой компоненте любую вершину $$$v$$$
  3. По лемме, выбрать в текущей компоненте из вершины $$$v$$$ любое хорошее ребро, и удалить его
  4. Второй на своем ходу либо проигрывает, если не может сходить, либо удаляет ребро $$$(a, b)$$$
  5. Если второй удалил ребро, он удалил его в компоненте с четным число ребер (по свойству хорошего ребра). И тогда возможны два случая:
    • Компонента, в которой находилось ребро $$$(a, b)$$$ осталась связна. Тогда там стало нечетное число ребер, и первый игрок выбирает в качестве вершины $$$v$$$ любую из вершин $$$a$$$ и $$$b$$$
    • Компонента, в которой находилось ребро $$$(a, b)$$$, распалась на две. Тогда ровно одна из двух получившихся компонент содержит нечетное число ребер. А $$$a$$$ и $$$b$$$ лежат в разных компонентах. Тогда в качестве $$$v$$$ первый игрок выберет из вершин $$$a$$$ и $$$b$$$ ту, которая лежит в компоненте с нечетным числом ребер
  6. Переходим к пункту 3

Первый игрок не может проиграть, потому что на его ходу в текущей компоненте нечетное число ребер (и поэтому по лемме он может выбрать хорошее ребро).

Доказательство леммы:

Можно заметить, что второй случай покрывает в том числе случай, если степень вершины $$$v$$$ равна $$$1$$$.

Таким образом, чтобы решить задачу, нужно пройтись по всем компонентам связности, например обходом в глубину, и проверить есть ли среди них та, что содержит нечетное число ребер. Итоговая сложность решения O($$$n + m$$$).