Проверка на двудольность
Материал из Algocode wiki
Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют еще двудольными.
С помощью обхода графа легко проверить граф на двудольность и даже вывести цвет каждой вершины - достаточно запустить dfs и просто красить вершины, 1 - в первый, все в которые ведут ребра во второй, затем снова в первый и так далее.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin