Ниже приведено краткое решение задачи: алгоритм за O(n + m), доказательство корректности и связь с 2‑SAT.

1) Алгоритм (BFS/DFS‑раскраска в 2 цвета)

Идея: для каждого компонента графа выполнить BFS (или DFS), раскрашивая вершины по уровням (двумя цветами 0 и 1). Смежную вершину раскрашиваем в противоположный цвет; если найдём ребро между вершинами одного цвета — граф не двудолен.

Псевдокод:

color[v] := UNCOLORED для всех vДля каждой вершины v:
если color[v] = UNCOLORED:
color[v] := 0положить v в очередь Qпока Q не пуста:u := извлечь(Q)для каждого соседа w вершины u:
если color[w] = UNCOLORED:
color[w] := 1 − color[u]; поместить w в Qиначе если color[w] = color[u]:
вернуть "не двудолен"вернуть "двудолен" и (при необходимости) полученную раскраску

Сложность: каждый ребро рассматривается O(1) раз с каждой стороны в итерациях — всего O(m), каждая вершина обрабатывается один раз — O(n). Итого O(n + m).

2) Доказательство корректности

Если алгоритм вернул "двудолен", то очевидно существует 2‑раскраска (color), и по определению это означает, что никакое ребро не соединяет вершины одного цвета → граф двудолен.

Обратно: если граф двудолен, то BFS/DFS никогда встретит конфликт, потому что при обходе по уровням сосед всегда должен иметь противоположный цвет, и такая раскраска существует для каждой компоненты, следовательно алгоритм не выдаст ложный "не двудолен".

Связь с нечётными циклами (классическое утверждение): граф двудолен тогда и только тогда, когда в нём нет цикла нечётной длины.

Если в графе есть цикл нечётной длины, то при попытке 2‑раскраски в цикле получится противоречие (последняя вершина должна иметь и тот же, и противоположный цвет исходной).Если при BFS/DFS найдено ребро u—v, у которых color[u] = color[v], то существует нечётный цикл: возьмём путь в дереве обхода между u и v и добавим ребро u—v; длина образованного цикла нечётна (потому что расстояния от корня до u и v имеют одинаковую чётность), значит граф не двудолен. Следовательно алгоритм обнаружит конфликт тогда, когда граф действительно недвудолен.

Таким образом алгоритм корректен и работает за O(n + m).

3) Связь между двудольностью и 2‑SAT

Построение 2‑SAT формулы, эквивалентной двуместной раскраске:
Для каждой вершины i введём булеву переменную x_i:
x_i = True означает, что вершина i в части A; x_i = False — в части B.
Для каждого ребра (i, j) требуется, чтобы вершины принадлежали разным частям: x_i ≠ x_j.
Условие x_i ≠ x_j можно эквивалентно записать в КНФ как две 2‑литерных дизъюнкции:
(x_i ∨ x_j) ∧ (¬x_i ∨ ¬x_j).
Действительно: эти два дизъюнкта запрещают одновременно x_i = x_j = False и x_i = x_j = True, т.е. оставляют только различающиеся значения.

Эквивалентность:

Если граф двудолен, то существует 2‑раскраска, которая задаёт удовлетворяющую замену переменных x_i (True/False по частям). Тогда для каждого ребра x_i ≠ x_j выполняется, значит сформулированная 2‑CNF удовлетворима.Если 2‑CNF удовлетворима, то любое удовлетворение даёт разделение вершин на те с x_i = True и те с x_i = False, причём по построению у каждого ребра значения различаются ⇒ это собственная 2‑раскраска графа ⇒ граф двудолен.

Размер формулы и время: для каждого ребра генерируются 2 дизъюнкта, значит формула имеет O(m) дизъюнктов и O(n) переменных. 2‑SAT проверяется за линейное время O(#переменных + #клауза) с помощью построения импликационного графа и поиска сильно связанных компонентов (алгоритм Косарайю/Тарьяна). Поэтому проверка двудольности через сведение к 2‑SAT также даёт линейное решение — но естественный BFS/DFS‑алгоритм проще и быстрее в реализации.

Короткое резюме:

Алгоритм: BFS/DFS с раскраской в два цвета по уровням, проверка конфликтов — корректен и работает за O(n + m).Теоретическая связь: граф двудолен ⇔ формула (для каждой вершины переменная x_i, для каждого ребра (x_i ∨ x_j) ∧ (¬x_i ∨ ¬x_j)) является удовлетворимой 2‑CNF.