Динамическое подключение | Набор 2 (DSU с откатом)
Динамическая связность, как правило, относится к хранению связности компонентов графа, где ребра меняются между некоторыми или всеми запросами. Основные операции –
- Добавьте ребро между узлами a и b
- Удалить ребро между узлами a и b
Типы проблем с использованием динамического подключения
Проблемы с использованием динамического подключения могут быть следующих форм:
- Добавлены только ребра (может называться «Инкрементное подключение») — используйте структуру данных DSU.
- Только удаленные ребра (может быть «Декрементная связность») — начните с графа в его конечном состоянии после удаления всех необходимых ребер. Обрабатывать запросы от последнего запроса к первому (в обратном порядке). Добавьте ребра в порядке, обратном их удалению.
- Добавление и удаление ребер (может называться «Полностью динамическое подключение») — для этого требуется функция отката для структуры DSU, которая может отменить изменения, внесенные в DSU, возвращая его к определенному моменту в его истории. Это называется DSU с откатом.
DSU с откатом
DSU с откатом выполняется в соответствии с приведенными ниже шагами, где история DSU может храниться с использованием стеков.
- В следующей реализации мы используем 2 стека :
- Один из стеков (стек 1) хранит указатель на позицию в массиве (ранговый массив или родительский массив), которую мы изменили, и
- В другом (стеке 2) мы сохраняем исходное значение, хранящееся в этой позиции (в качестве альтернативы мы можем использовать один стек структуры, подобной парам в C++).
- Чтобы отменить последнее изменение, внесенное в DSU, установите значение в месте, указанном указателем в верхней части стека 1 , на значение в верхней части стека 2 . Извлеките элемент из обоих стеков.
- Каждая точка в истории модификации графа однозначно определяется длиной стека после окончательной модификации для достижения этого состояния.
- Итак, если мы хотим отменить некоторые изменения для достижения определенного состояния, все, что нам нужно знать, — это длина стека в этой точке. Затем мы можем извлекать элементы из стека и отменять эти изменения до тех пор, пока стек не станет необходимой длины.
Код универсальной реализации выглядит следующим образом:
C++
#include <iostream>using namespace std; const int MAX_N = 1000;int sz = 0, v[MAX_N], p[MAX_N], r[MAX_N];int* t[MAX_N]; void update(int* a, int b){ if (*a != b) { t[sz] = a; v[sz] = *a; *a = b; sz++; }} void rollback(int x){ // Undo the changes made, // until the stack has length sz for (; sz > x;) { sz--; *t[sz] = v[sz]; }} int find(int n){ return p[n] ? find(p[n]) : n;} void merge(int a, int b){ // Parent elements of a and b a = find(a), b = find(b); if (a == b) return; // Merge small to big if (r[b] > r[a]) std::swap(a, b); // Update the rank update(r + a, r[a] + r[b]); // Update the parent element update(p + b, a);} int main(){ return 0;} |
Пример для понимания динамического подключения
Давайте рассмотрим пример для лучшего понимания концепции
Given a graph with N nodes (labelled from 1 to N) and no edges initially, and Q queries. Each query either adds or removes an edge to the graph. Our task is to report the number of connected components after each query is processed (Q lines of output). Each query is of the form {i, a, b} where
- if i = 1 then an edge between a and b is added
- If i = 2, then an edge between a and b is removed
Примеры
Input: N = 3, Q = 4, queries = { {1, 1, 2}, {1, 2, 3}, {2, 1, 2}, {2, 2, 3} }
Output: 2 1 2 3
Explanation:The image shows how the graph changes in each of the 4 queries, and how many connected components there are in the graph.
Input: N = 5, Q = 7, queries = { {1, 1, 2}, {1, 3, 4}, {1, 2, 3}, {1, 1, 4}, {2, 2, 1}, {1, 4, 5}, {2, 3, 4} }
Output: 4 3 2 2 2 1 2
Explanation:The image shows how the graph changes in each of the 7 queries, and how many connected components there are in the graph.
Подход: проблема может быть решена с помощью комбинации DSU с откатом и подходом «разделяй и властвуй», основанным на следующей идее:
The queries can be solved offline. Think of the Q queries as a timeline.
- For each edge, that was at some point a part of the graph, store the disjoint intervals in the timeline where this edge exists in the graph.
- Maintain a DSU with rollback to add and remove edges from the graph.
Подход «разделяй и властвуй» будет использоваться на временной шкале запросов. Функция будет вызываться для интервалов (l, r) на временной шкале запросов. что будет:
- Добавьте все ребра, которые присутствуют в графе для всего интервала (l, r) .
- Рекурсивно вызовите ту же функцию для интервалов (l, mid) и (mid+1, r) [если интервал (l, r) имеет длину 1 , ответьте на l -й запрос и сохраните его в массиве ответов).
- Вызовите функцию отката, чтобы восстановить граф в его состояние на момент вызова функции.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(Q * logQ * logN)
- Анализ: Пусть изначально в графе существует M ребер.
- Общее количество ребер, которые могут существовать в графе, равно M+Q (ребро добавляется при каждом запросе, ни одно ребро не удаляется).
- Общее количество операций добавления и удаления ребер составляет O((M+Q) log Q) , и каждая операция занимает logN времени.
- В приведенной выше задаче M = 0 . Таким образом, временная сложность этого алгоритма составляет O(Q * logQ * logN).
Вспомогательное пространство: O(N+Q)