В контексте графов, система непересекающихся множеств напрямую решает следующую задачу:
Задача. Дан изначально пустой граф, и требуется обработать $n$ запросов добавления ребра (+) и проверки связности двух вершин (?).
Если немного подумать, можно решить и обратную ей:
Задача. Дан граф, и нужно обрабатывать $n$ заранее известных запросов удаления ребра (-) и проверки связности двух вершин (?).
Здесь ключевое условие — что все запросы известны заранее. Это позволяет заменить все - на + и пройтись по всем запросам в обратном порядке. Если в конце граф становится пустым, то это будет эквивалентно предыдущей задаче, а если же граф удаляется не полностью, то все неудаленные ребра нужно просто добавить в СНМ в самом начале.
Если же есть одновременно и добавления, и удаления, то задача сильно усложняется. Если на запросы нужно отвечать в режиме онлайн, то для этого существует весьма сложная структура, называемая Lunk-Cut Tree, которую мы в этой статье разбирать не будем. Но если запросы известны заранее, можно применить уже известные методы декомпозиции запросов и откатывания структур.
#Dynamic Connectivity Problem
Задача. Дан изначально пустой граф, и нужно отвечать на $n$ заранее известных запросов добавления ребра (+), удаления ребра (-) и проверки связности двух вершин (?).
Попытаемся решить задачу корневой декомпозицией запросов. Разделим запросы на корневые блоки, и для каждого блока построим СНМ только для тех ребер, которые существуют на всем блоке.
Для ответа на каждый запрос добавим все недостающие ребра на текущем блоке в СНМ, сделаем непосредственно запрос к нему, а затем — важно — откатим все изменения, которые мы делали на текущем блоке, чтобы получить чистый СНМ, который можно таким же образом использовать для других запросов текущего блока.
Как откатывать СНМ? Можно воспользоваться либо трюком с занулением (только здесь «нулём» будет состояние СНМ для начала блока), либо поддерживать список изменений и проходиться по нему в обратном порядке.
Асимптотика операций СНМ, правда, немного поменяется. Амортизация через сжатие путей в худшем случае выгоды не даст — можно много раз заставлять структуру делать сжатие и затем откатываться на состояние до него. Поэтому остается только весовая или ранговая эвристика, и асимптотика с ней будет $O(\log n)$.
Такое решение будет работать за $O(n \sqrt n \log n)$, однако можно быстрее.
#Divide-and-conquer по запросам
Давайте вместо корневой эвристики заведем рекурсивную функцию solve(l, r), которая будет отвечать на все запросы с $l$ по $r$, имея СНМ, соответствующий всем ребрам, которые существуют на всем этом промежутке.
Эта функция будет действовать следующим образом:
- Если в промежутке всего один запрос, то найдем ответ на него через СНМ и выйдем. В противном случае:
- Разделим промежуток времени пополам:
t = (l + r / 2). - Рекурсивно разрешим левую половину:
solve(l, t). - Добавим в СНМ те ребра, которые существуют на всей правой половине запросов.
- Рекурсивно запустимся от правой половины:
solve(t, r). - Откатим СНМ до изначального состояния.
Так как мы всегда поддерживаем инвариант «когда мы запускаемся и выходим из рекурсии, СНМ всегда чистый для этого промежутка», алгоритм действительно ответит на все запросы и будет работать за $O(n \log^2 n)$.
Заметим, что мы нигде не использовали ничего конкретно про связность — можно отвечать на любые запросы, поддерживаемые СНМ, например о размерах компонент или числе ребер. Также существуют модификации для других задач, например для нахождения мостов или компонент двусвязности — подробнее можно почитать в дипломной работе Сергея Копелиовича.