Объявите массив which размером, равным количеству вершин, устанавливая каждый элемент в 0 изначально.Затем выполните поиск в глубине по графику, записав «номер уровня», на котором вы находитесь на ходу.Это начинается в 1, и чередуется между 1 и 2 с каждым пройденным краем.Для каждой достигнутой вершины присвойте текущий уровень соответствующей записи which и (если ранее было 0) рекурсивно обрабатывайте ее дочерние элементы.После этого все элементы which будут равны либо 1, либо 2, а which[i] указывает, к какой вершине принадлежит i.
Интуитивно можно представить, что каждый переход от родителя к потомку в DFSподнимает вас «вниз» на уровень, а каждый обратный ход возвращает вас «вверх».Благодаря свойству двудольных, все вершины на четных уровнях могут быть связаны только с вершинами на нечетных уровнях и наоборот, поэтому достаточно пометить узлы "четный" или "нечетный", чтобы разделить их на два набора.График содержит более одного компонента, вам, конечно, потребуется отдельный DFS для каждого компонента.