Проверка на двудольность

Условие

Вам дан неориентированный граф. Проверьте, является ли он двудольным, и если да — выведите его стороны.

Решение

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

Используем DFS (можно также, как в предыдущей задаче, использовать BFS), начиная с каждой вершины, которая ещё не была посещена. В каждом поиске вершину, с которой мы начинаем, назначаем стороной 1 (например, цветом 0). Каждый раз, когда мы посещаем ещё не посещённого соседа вершины одной стороны, назначаем его другой стороне.

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

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