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

O(V+E)

Красим граф в два цвета через BFS/DFS: стартовый узел получает один цвет, каждый сосед - другой, и так дальше наружу. Если дошли до ребра, чьи два конца уже одного цвета, это доказывает цикл нечётной длины, и разбиения на две стороны не существует.

Сигналы

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

Шаблон

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

Похоже, но не то

Компоненты связности: Раскраска в два цвета проверяет отсутствие конфликта внутри группы и отсутствие нечётного цикла, это больше, чем просто подсчёт числа отдельных групп.
Union-find: Union-find говорит, что с чем связано, но не имеет понятия о 'противоположной стороне', поэтому не может поймать нечётный цикл. Именно раскраска в два цвета плюс проверка совпадения цвета на ребре это ловит.

V, E до ~1e5, конфликтующие пары нужно разбить на две группы -> O(V+E): проход BFS/DFS с раскраской в два цвета посещает каждый узел и ребро один раз и быстро останавливается на первом одноцветном ребре.

Изучить этот паттерн