dcp.md

title	Динамическая связность
authors	Сергей Слотин
date	2021-09-25 00:00:00 UTC
prerequisites	/cs/set-structures/dsu /cs/persistent/persistent-array /cs/decomposition/rollback

В контексте графов, система непересекающихся множеств напрямую решает следующую задачу:

Задача. Дан изначально пустой граф, и требуется обработать $n$ запросов добавления ребра (+) и проверки связности двух вершин (?).

Если немного подумать, можно решить и обратную ей:

Задача. Дан граф, и нужно обрабатывать $n$ заранее известных запросов удаления ребра (-) и проверки связности двух вершин (?).

Здесь ключевое условие — что все запросы известны заранее. Это позволяет заменить все - на + и пройтись по всем запросам в обратном порядке. Если в конце граф становится пустым, то это будет эквивалентно предыдущей задаче, а если же граф удаляется не полностью, то все неудаленные ребра нужно просто добавить в СНМ в самом начале.

Если же есть одновременно и добавления, и удаления, то задача сильно усложняется. Если на запросы нужно отвечать в режиме онлайн, то для этого существует весьма сложная структура, называемая Lunk-Cut Tree, которую мы в этой статье разбирать не будем. Но если запросы известны заранее, можно применить уже известные методы декомпозиции запросов и откатывания структур.

Dynamic Connectivity Problem

Задача. Дан изначально пустой граф, и нужно отвечать на $n$ заранее известных запросов добавления ребра (+), удаления ребра (-) и проверки связности двух вершин (?).

Попытаемся решить задачу корневой декомпозицией запросов. Разделим запросы на корневые блоки, и для каждого блока построим СНМ только для тех ребер, которые существуют на всем блоке.

Для ответа на каждый запрос добавим все недостающие ребра на текущем блоке в СНМ, сделаем непосредственно запрос к нему, а затем — важно — откатим все изменения, которые мы делали на текущем блоке, чтобы получить чистый СНМ, который можно таким же образом использовать для других запросов текущего блока.

Как откатывать СНМ? Можно воспользоваться либо трюком с занулением (только здесь «нулём» будет состояние СНМ для начала блока), либо поддерживать список изменений и проходиться по нему в обратном порядке.

Асимптотика операций СНМ, правда, немного поменяется. Амортизация через сжатие путей в худшем случае выгоды не даст — можно много раз заставлять структуру делать сжатие и затем откатываться на состояние до него. Поэтому остается только весовая или ранговая эвристика, и асимптотика с ней будет $O(\log n)$.

Такое решение будет работать за $O(n \sqrt n \log n)$, однако можно быстрее.

Divide-and-conquer по запросам

Давайте вместо корневой эвристики заведём дерево отрезков, в вершинах которого сохраним все рёбра, существующие целиком на всём отрезке этой вершины и не существующие целиком на отрезке её предка. Таким образом каждое ребро окажется не более чем в $log(n)$ вершинах ДО.

Рёбра, имеющие несколько отрезков жизни можно считать разными рёбрами и добавлять в ДО независимо, т. к. эти отрезки не пересекаются, а также их суммарное количество будет не более $n$.

Чтобы найти ответ, можно пройтись по дереву отрезков такой dfs(v):

0. Добавим в СНМ рёбра из тек. вершины ДО $v$. 1.0. Если отрезок единичной длины, ответим на все его запросы, 1.1. Иначе запустимся в левого, а затем и в правого ребёнка.
1. Откатим все добавленные из тек. вершины $v$ в СНМ рёбра.

Несложно заметить, что асимптотика алгоритма $O(n \log^2 n)$, потому что каждое из не более $n$ рёбер мы добавим в не более чем $log(n)$ отрезком ДО, в каждый отрезок зайдём ровно по 1 разу и каждое ребро из него добавим в СНМ за $O(log(n))$.

Заметим, что мы нигде не использовали ничего конкретно про связность — можно отвечать на любые запросы, поддерживаемые СНМ, например о размерах компонент или числе ребер. Также существуют модификации для других задач, например для нахождения мостов или компонент двусвязности — подробнее можно почитать в дипломной работе Сергея Копелиовича.