Где применяется
1. Задача
Ты распределяешь задачи по двум машинам. Некоторым парам задач нельзя работать на одной машине: например, они пишут в один и тот же файл или одна должна закончиться до старта другой. Каждое такое правило «держи их порознь» назовём конфликтом.
Можно ли отправить каждую задачу на одну из двух машин так, чтобы ни одна конфликтующая пара не оказалась вместе? Иногда можно. Иногда конфликты замыкаются в кольцо, и любое разбиение на две части невозможно. Узнать, какой у тебя случай, нужно до того, как ты пообещаешь расписание.
Тот же вопрос встречается при разбиении на два лагеря, при расстановке людей по двум сменам и при распределении по двум комнатам. Конфликты образуют граф. Вопрос в том, делится ли этот граф на две части так, чтобы внутри каждой части не было ни одного ребра.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитisBipartite(7, {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [2, 0], 4: [5, 6], 5: [4, 6], 6: [4, 5]})start
Проверяем, можно ли разбить вершины на две стороны так, чтобы каждое ребро шло между ними. В начале у всех color = -1, цвета нет.
Как узнать
Эти слова в условии значат этот паттерн
- разбить на две группы без конфликта внутри группы
- раскрасить граф в два цвета
- обнаружить цикл нечётной длины
- мы против них / расписание на две смены / распределение по двум комнатам
- возможно ли двудольное разбиение конфликтующих пар
Похоже, но не то
- Обход графа BFS / DFS (Graph BFS / DFS)
Сам обход точно такой же. Добавился только цвет, который несёт каждая вершина.
- Компоненты связности (Connected components)
Оба перебирают непосещённые вершины и запускают обход. Здесь обход ещё и может провалиться.
- Система непересекающихся множеств (Union-find (disjoint set))
Взвешенное непересекающееся множество отвечает на тот же вопрос. Оно удобно, когда рёбра приходят со временем.
- Бэктрекинг (Backtracking)
Для трёх и более цветов нужен перебор с откатом. Двум цветам выбор не нужен вовсе.
V вершин и E рёбер дают O(V + E). Каждая вершина красится один раз, каждое ребро проверяется дважды.
На LeetCode
Задачи, где нужно понять, делятся ли люди, вершины или предметы на две группы так, чтобы каждый конфликт шёл между группами. Покрась стартовую вершину, дай каждому соседу другой цвет, и сосед, уже покрашенный в твой цвет, значит, что разбиения нет.
Это задача урока. Граф может состоять из нескольких частей, так что запускай раскраску из каждой ещё не покрашенной вершины.
Каждая неприязнь это ребро между двумя людьми, и ответ true ровно тогда, когда граф красится в два цвета.
Если хоть одна компонента не красится в два цвета, ответ минус 1. Иначе запусти BFS из каждой её вершины, возьми наибольшее число уровней и сложи по компонентам.