Починка цепочки

Автор задачи: Даниил Орешников, разработчик: Николай Будин

Для начала, переформулируем задачу в терминах теории графов. Дан граф из $$$n$$$ вершин и $$$m$$$ ребер. Изначально все вершины покрашены в белый цвет. За один ход можно:

Требуется сделать минимальное число операций, чтобы граф стал выглядеть как простой путь $$$1$$$, $$$2$$$, ..., $$$n$$$. И все вершины были белыми.

Несложно заметить, что к каждой вершине нужно максимум один раз применять первую операцию. И если к вершине применили первую операцию, то к ней нужно применить и вторую. Следовательно, нужно выбрать минимальное по размеру множество вершин, что если ко всем ним применить первые операции, все оставшиеся в графе ребра будут соединять соседние по номерам вершины. Эта задача может быть решена за время $$$O(2^n \cdot n)$$$ с помощью перебора всех вариантов выбора множества вершин, к которым будут применены операции. Это решение может быть соптимизировано до времени $$$O(2^{\frac{n}{2}} \cdot n)$$$ с помощью метода meet in the middle.