Войти Регистрация
Алгоритмы

196. Две смены модерации без спорных пар

Средняя

В команде модерации Авито n человек, номера от 0 до n − 1. Пара [a, b] в conflicts значит, что a и b проверяют работу друг друга и не должны сидеть в одной смене.

Можно ли разбить всех на две смены (любого размера), чтобы ни одна пара из conflicts не оказалась в одной? Верните True или False.

В работе: Перекрёстная проверка решений: 1200 модераторов и 5000 пар «проверяющий — проверяемый». Перебор всех разбиений — 2¹²⁰⁰ вариантов, раскраска — миллисекунды.

Пример 1

Ввод
n = 4
conflicts = [[0, 1], [1, 2], [2, 3], [3, 0]]
Вывод
True

Смены {0, 2} и {1, 3}.

Пример 2

Ввод
n = 3
conflicts = [[0, 1], [1, 2], [2, 0]]
Вывод
False

Треугольник: третий человек всегда попадёт к одному из двух других.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 0 ≤ длина conflicts ≤ 2·10⁵
  • a ≠ b, пары могут повторяться
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def two_shifts(n, conflicts):
ГрафыBFSДвудольный графцельO(n)

Источник: наша задача на данных Авито. Условие пересказано своими словами.