---
title: "Проверка двудольности (раскраска в два цвета)"
url: https://algopath.pro/ru/patterns/bipartite
language: ru
summary: "Покрасьте любую вершину, а потом покрасьте каждого её соседа в другой цвет. Конфликт доказывает, что граф не двудольный."
updated: 2026-08-24
---

# Проверка двудольности (раскраска в два цвета)

Покрасьте любую вершину, а потом покрасьте каждого её соседа в другой цвет. Конфликт доказывает, что граф не двудольный.

## Проверка двудольности (раскраска в два цвета): как это работает?

В начале все вершины без цвета. Дальше пройдите по ним всем.

Непокрашенная вершина открывает новый обход. Покрасьте её первым цветом.

Обойдите её соседей по очереди. Непокрашенного соседа красьте в противоположный цвет.

Уже покрашенный сосед обязан отличаться от текущей вершины. Если цвета совпали, граф не проходит.

Конфликт означает, что где-то есть нечётный цикл. Никакая раскраска в два цвета его не переживёт.

Повторите для каждой компоненты. Граф двудольный, только если прошли все.

- `цвет[0] = A` Граф это треугольник: 0-1, 1-2 и 2-0.
- `цвет[1] = B` Сосед получает другой цвет.
- `цвет[2] = A` Вершина 2 соседствует с 1, поэтому берёт A.
- `ребро 2-0: A против A` На обоих концах один цвет. Проверка провалилась.
- `ответ = ложь` Треугольник это нечётный цикл. Два цвета в него не помещаются.

## Проверка двудольности (раскраска в два цвета): когда применять?

- разбить на две группы без конфликта внутри группы
- раскрасить граф в два цвета
- обнаружить цикл нечётной длины
- мы против них / расписание на две смены / распределение по двум комнатам
- возможно ли двудольное разбиение конфликтующих пар

## Проверка двудольности (раскраска в два цвета): с чем путают?

- **Обход графа BFS / DFS** - Сам обход точно такой же. Добавился только цвет, который несёт каждая вершина.
- **Компоненты связности** - Оба перебирают непосещённые вершины и запускают обход. Здесь обход ещё и может провалиться.
- **Система непересекающихся множеств** - Взвешенное непересекающееся множество отвечает на тот же вопрос. Оно удобно, когда рёбра приходят со временем.
- **Бэктрекинг** - Для трёх и более цветов нужен перебор с откатом. Двум цветам выбор не нужен вовсе.

## Проверка двудольности (раскраска в два цвета): сложность по времени и памяти

V вершин и E рёбер дают O(V + E). Каждая вершина красится один раз, каждое ребро проверяется дважды.

## Проверка двудольности (раскраска в два цвета): разбор примера

### Разделить людей на две группы

Дано число людей и список пар, которые не выносят друг друга.

Разделите всех на две группы. В одной группе не должно оказаться двух неприятных друг другу людей.

Каждый человек это вершина, а каждая неприязнь это ребро.

Запустите раскраску в два цвета по всем компонентам. Один конфликт делает разделение невозможным.

```javascript
function possibleBipartition(n, dislikes) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of dislikes) {
        graph[a].push(b);
        graph[b].push(a);
    }

    const colour = new Array(n + 1).fill(0);

    for (let start = 1; start <= n; start++) {
        if (colour[start] !== 0) continue; // already placed by an earlier walk

        colour[start] = 1;
        const queue = [start];

        for (let i = 0; i < queue.length; i++) {
            const node = queue[i];

            for (const next of graph[node]) {
                if (colour[next] === colour[node]) return false; // same side
                if (colour[next] === 0) {
                    colour[next] = -colour[node];
                    queue.push(next);
                }
            }
        }
    }

    return true;
}
```

## Проверка двудольности (раскраска в два цвета): частые ошибки

- **Идут только от первой вершины** В несвязном графе конфликт может прятаться в другой части. Запускайте обход из каждой непокрашенной вершины.
- **Хранят только флаг посещения** Нужен цвет, а не просто факт посещения. Один массив может нести и то, и другое.
- **Красят при извлечении из очереди** Тогда вершина попадает в очередь дважды с разными цветами. Красьте её при вставке.
- **Ждут, что провал выглядит как-то особенно** Единственная его причина это нечётный цикл. Граф только с чётными циклами проходит всегда.

## Проверка двудольности (раскраска в два цвета): задачи с собеседований

- **Двудольный ли граф** Чистая форма, по списку смежности.
- **Возможное разбиение на две группы** Рёбрами становятся пары неприязни.
- **Разделение игроков на две команды** Та же раскраска в два цвета, другими словами.
- **Поиск нечётного цикла** Та же проверка, заданная с другой стороны.
- **Максимальное паросочетание в двудольном графе** Имеет смысл, только когда доли уже известны.
- **Посадка цветов без одинаковых соседей** Четыре цвета, поэтому хватает жадного прохода.
- **Раскраска графа в три цвета** Бэктрекинг, поскольку двух цветов уже не хватает.

## JavaScript

```javascript
function isBipartite(n, adj) {
    const color = new Array(n).fill(-1);
    for (let start = 0; start < n; start++) {
        if (color[start] !== -1) continue;
        color[start] = 0;
        const queue = [start];
        while (queue.length) {
            const node = queue.shift();
            for (const next of adj[node] || []) {
                if (color[next] === -1) {
                    color[next] = 1 - color[node];
                    queue.push(next);
                } else if (color[next] === color[node]) {
                    return false; // same color on both ends: odd cycle
                }
            }
        }
    }
    return true;
}
```

## Python

```python
from collections import deque

def is_bipartite(n, adj):
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in adj.get(node, []):
                if color[nxt] == -1:
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False  # same color on both ends: odd cycle
    return True
```

## PHP

```php
function isBipartite(int $n, array $adj): bool {
    $color = array_fill(0, $n, -1);
    for ($start = 0; $start < $n; $start++) {
        if ($color[$start] !== -1) continue;
        $color[$start] = 0;
        $queue = [$start];
        while ($queue) {
            $node = array_shift($queue);
            foreach ($adj[$node] ?? [] as $next) {
                if ($color[$next] === -1) {
                    $color[$next] = 1 - $color[$node];
                    $queue[] = $next;
                } elseif ($color[$next] === $color[$node]) {
                    return false; // same color on both ends: odd cycle
                }
            }
        }
    }
    return true;
}
```