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

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

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

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

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

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

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

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

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

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;
}

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

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

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

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

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

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

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;
}

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

Эти формулировки в условии ведут сюда:

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

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

• Обход графа BFS / DFS (Graph BFS / DFS): Сам обход точно такой же. Добавился только цвет, который несёт каждая вершина.
• Компоненты связности (Connected components): Оба перебирают непосещённые вершины и запускают обход. Здесь обход ещё и может провалиться.
• Система непересекающихся множеств (Union-find (disjoint set)): Взвешенное непересекающееся множество отвечает на тот же вопрос. Оно удобно, когда рёбра приходят со временем.
• Бэктрекинг (Backtracking): Для трёх и более цветов нужен перебор с откатом. Двум цветам выбор не нужен вовсе.

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

• Идут только от первой вершины

  В несвязном графе конфликт может прятаться в другой части. Запускайте обход из каждой непокрашенной вершины.

• Хранят только флаг посещения

  Нужен цвет, а не просто факт посещения. Один массив может нести и то, и другое.

• Красят при извлечении из очереди

  Тогда вершина попадает в очередь дважды с разными цветами. Красьте её при вставке.

• Ждут, что провал выглядит как-то особенно

  Единственная его причина это нечётный цикл. Граф только с чётными циклами проходит всегда.

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

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

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

O(V+E)

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