|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 13-2. Банкет
(Разбор)
Построим граф, в котором вершинами будут ОВП. Ребрами соединим те пары ОВП, которые не могут сидеть за одним столом. Обойдем получившийся граф в глубину, раскрашивая вершины в два цвета. Цвет в терминах нашей задачи будет обозначать номер стола для соответствующей ОВП. Переходя на следующий уровень рекурсии, будем менять цвет, в который мы красим вершину. Если в результате такой раскраски никакое ребро не соединяет две вершины одного цвета, то мы получили искомый способ рассадить ОВП по двум столам, иначе такого способа не существует. Это следует из того факта, что способ их рассадить существует тогда и только тогда, когда в полученном графе нет циклов нечетной длины.