Двудольный граф
Двудольный граф - граф, вершины которого можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств.
Часто в контексте двудольных графов используется понятие цвета вершины. Разбитие графа на две доли называется покраской его вершин в два различных цвета. Каждое ребро должно соединять вершины различного цвета.
Для проверки графа на двудольность и разбития его на доли чаще всего используется DFS.
Алгоритм
Начинаем покраску с произвольной вершины, которую красим в произвольный цвет.
При прохождении по каждому ребру красим следующую вершину в противоположный цвет.
Если при переборе соседних вершин мы нашли вершину, уже покрашенную в тот же цвет, что и текущая, то в графе существует нечётный цикл, а значит, он не является двудольным.