Автор задачи и разработчик: Даниил Орешников
Эта задача — один из примеров не самых стандартных сведений ответа к решению 2-SAT. Догадаться до этого можно было по следующему факту: перед нами стоит множество выборов из двух опций, при этом из каждой пары опций ровно одна должна быть выбрана.
Для начала упростим условие: дан ориентированный граф на $$$n$$$ вершинах, в которой из каждой вершины выходит ровно два ребра, и в каждую вершину входит ровно два ребра, то есть $$$\mathtt{deg}_\mathrm{in}(v) = \mathtt{deg}_\mathrm{out}(v) = 2$$$ для всех $$$v$$$. Требуется выбрать несколько циклов, покрывающих все вершины по одому разу, при чем чтобы интервалы чисел на выбранных ребрах имели общее непустое пересечение.
Сразу будем описывать сведение задачи к 2-SAT, то есть к решению логической формулы в 2-КНФ, в которой несколько клозов (скобок, состоящих из логического «ИЛИ» двух переменных или их отрицаний) перечислены через логическое «И». Для этого поймем, как описать в терминах 2-SAT условия задачи. Вместо «ИЛИ» будем использовать следствия (импликации), так как их можно взаимно выразить друг из друга, а решение задачи 2-SAT строится как раз на импликациях.
Заметим, что построенная формула полностью описывает все условия из задачи. И любое решение этой формулы однозначно транслируется в корректный ответ для нашей задачи. Только надо не забывать, что когда мы добавляем следствие $$$a \to b$$$, надо также добавить и равнозначное ему $$$\lnot b \to \lnot a$$$.
Теперь, для решения этой формулы, применим стандартный алгоритм решения 2-SAT, основанный на выделении компонет сильной связности. Если мы получили противоречие, то решения нет, а иначе — выбираем те $$$e_i$$$, которые истинны, и получаем список выбранных ребер, а также выбираем максимальное $$$c$$$, при котором $$$m_c$$$ истинно, и получаем значение $$$m$$$. Суммарное время работы алгоритма равно $$$\mathcal{O}(n + m_{\max})$$$.