5
правок
Изменения
Нет описания правки
'''Динамическая связность''' (англ. ''dynamic connectivity'') {{---}} задача обработки запросов на добавление и удаление рёбер в неориентированном графе, а также проверки, лежат ли какие-то вершины в одной компоненте связности.
В этой статье приведено решение задачи в offline, то есть ответы на все запросы будут получены после обработки всех запросов, а не по мере их поступления.
== Постановка задачи ==
'''using''' '''namespace''' std;
'''typedef''' pair < '''int''' , '''int''' > ipair;
'''const ''' '''int''' N = 100321;
<font color="green">// СНМ</font>
** Размер компоненты связности, которая содержит вершину <tex>v</tex>
** Количество компонент связности
* Эту идею можно использовать и для других задач. Вместо СНМ можно использовать любую структуру данных, в которую можно добавлять, но не удалять.
** Например, динамический рюкзак: добавлять предмет в него можно за <tex>O(w)</tex> (<tex>w</tex> {{---}} максимальный вес), а удалять нельзя. Аналогично тому, как в dynamic connectivity offline добавляются и удаляются рёбра, можно удалять элементы из рюкзака.
