Проверка двудольности графа раскраской BFS: как поймать нечётный цикл?
Нужно проверить, является ли неориентированный граф двудольным (вершины можно покрасить в 2 цвета так, чтобы концы каждого ребра были разного цвета). Понимаю, что это связано с нечётными циклами. Как проверить двудольность через BFS-раскраску и при чём тут компоненты связности?
2 ответа
Граф двудольный ⇔ в нём нет циклов нечётной длины. BFS-раскраска проверяет это напрямую: красим стартовую вершину в 0, всех соседей — в 1, их соседей — в 0 и т.д. Если встретили ребро между вершинами одного цвета — нашли нечётный цикл, граф не двудольный.
bool isBipartite(int n, vector<int> g[]) {
vector<int> color(n, -1);
for (int s = 0; s < n; s++) { // обходим КАЖДУЮ компоненту
if (color[s] != -1) continue;
color[s] = 0;
queue<int> q; q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : g[v]) {
if (color[u] == -1) { color[u] = color[v] ^ 1; q.push(u); }
else if (color[u] == color[v]) return false; // конфликт
}
}
}
return true;
}
При чём тут компоненты: граф может быть несвязным, поэтому внешний цикл for s запускает BFS из каждой непокрашенной вершины — каждая компонента красится независимо. Граф двудолен ⇔ двудольна каждая компонента.
Сложность O(V+E), память O(V). color[v] ^ 1 элегантно переключает 0↔1.
Грабля: петля (ребро v–v) сразу делает граф недвудольным (нечётный цикл длины 1) — стандартный код это поймает, т.к. color[v] == color[v].
Тот же алгоритм можно писать DFS-ом — разницы для факта двудольности нет. Но BFS удобнее, если заодно нужно восстановить нечётный цикл как контрпример: BFS даёт дерево кратчайших путей, и при конфликте на ребре (v,u) цикл собирается из путей от LCA(v,u) в BFS-дереве + само ребро — он гарантированно нечётной длины.
Ещё двудольность эквивалентна тому, что СНМ-вариант (DSU на чётностях / weighted DSU) не находит противоречия — это удобно для динамической задачи, где рёбра добавляются по одному и надо отвечать «осталась ли двудольность». Для статической задачи BFS-раскраска — самое простое и быстрое.