Изменения

'''Динамическая связность''' (англ. ''dynamic connectivity'') {{---}} задача обработки Задача|definition = Имеется [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов на добавление трёх типов:* добавить ребро между вершинами <tex>u</tex> и удаление рёбер в неориентированном графе<tex>v</tex>,* удалить ребро между вершинами <tex>u</tex> и <tex>v</tex>, а также проверки* проверить, лежат ли какие-то вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.В графе могут быть кратные рёбра и петли.}}

Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]: каждая . Каждая компонента связности {{---}} это одно множество в СНМ, и при добавлении рёбер они объединяются.

Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]], в каждой его вершине будем хранить список пар. Каждый из отрезков <tex>i</tex>-е рёбро графа нужно добавить на отрезок <tex>[L_i,R_i]</tex> разобьём на отрезки, соответствующие вершинам дерева отрезков (. Это делается аналогично тому, как выполняется запрос в дереве отрезков происходит добавление на отрезке (процесс описан в дереве отрезковстатье "[[Несогласованные поддеревья. Реализация массового обновления]]") и запишем в соответствующие вершины пару , но без <tex>u_i,v_ipush</tex> (в каждой вершине дерева хранится массив пар). Теперь чтобы узнать, какие рёбра существуют во время выполнения : нужно спуститься по дереву от корня и записать пару <tex>iu_i,v_i</tex>-го запроса, достаточно посмотреть на путь от корня в вершины дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.

Будем использовать систему непересекающихся множествТеперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.  === Ответы на запросы ===Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в СНМ граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить СНМ граф к состоянию, которое было при входе (об этом ниже). Когда мы добираемся до листа, в СНМ граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ. Для поддержания такого графа и ответа на запросы будем использовать [[СНМ (реализация с помощью леса корневых деревьев)|систему непересекающихся множеств]]. При добавлении рёбер в граф объединим соответствующие множества в СНМ. Откатывание состояния СНМ описано ниже.

Как Для того, чтобы иметь возможность откатывать состояние СНМ? Каждый раз, когда мы изменяем что-то нужно при каждом изменении любого значения в СНМ, будем записывать в специальный массив, что именно мы изменили изменилось и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).

Каждое из <tex>O(m)</tex> рёбер записывается в <tex>O(\log m)</tex> вершин дерева отрезков. Поэтому операций <tex>\mathrm{union}</tex> в СНМ будет <tex>O(m \log m)</tex>. Каждая выполняется за <tex>O(\log n)</tex> (СНМ с ранговой эвристикой). Откаты не влияют на время работы.