Задача о динамической связности оффлайн — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал Dynamic connectivity offline в Задача о динамической связности оффлайн: импортозамещение)
(Очевидно некорректная оценка)
(не показаны 2 промежуточные версии 1 участника)
Строка 1: Строка 1:
'''Динамическая связность''' (англ. ''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> в одной компоненте связности.
 +
В графе могут быть кратные рёбра и петли.
 +
}}
 
В этой статье приведено решение задачи в offline, то есть ответы на все запросы будут получены после обработки всех запросов, а не по мере их поступления.
 
В этой статье приведено решение задачи в offline, то есть ответы на все запросы будут получены после обработки всех запросов, а не по мере их поступления.
 
== Постановка задачи ==
 
Имеется неориентированный граф из <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>O(m \cdot \alpha (n))</tex>, где <tex>\alpha</tex> {{---}} [[СНМ (реализация с помощью леса корневых деревьев)#Функция Аккермана|обратная функция Аккермана]].
 
Время работы такого решения: <tex>O(m \cdot \alpha (n))</tex>, где <tex>\alpha</tex> {{---}} [[СНМ (реализация с помощью леса корневых деревьев)#Функция Аккермана|обратная функция Аккермана]].
  
 
== Алгоритм ==
 
== Алгоритм ==
 +
=== Построение дерева отрезков ===
 
Рассмотрим массив запросов. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.
 
Рассмотрим массив запросов. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.
  
 
Пусть есть <tex>k</tex> рёбер, <tex>i</tex>-е соединяет вершины <tex>v_i</tex> и <tex>u_i</tex>, было добавлено запросом <tex>L_i</tex> и удалено запросом <tex>R_i</tex>.
 
Пусть есть <tex>k</tex> рёбер, <tex>i</tex>-е соединяет вершины <tex>v_i</tex> и <tex>u_i</tex>, было добавлено запросом <tex>L_i</tex> и удалено запросом <tex>R_i</tex>.
  
Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]]. Каждый из отрезков <tex>[L_i,R_i]</tex> разобьём на отрезки, соответствующие вершинам дерева отрезков (аналогично тому, как выполняется запрос на отрезке в дереве отрезков) и запишем в соответствующие вершины пару <tex>u_i,v_i</tex> (в каждой вершине дерева хранится массив пар). Теперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
+
Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]], в каждой его вершине будем хранить список пар. <tex>i</tex>-е рёбро графа нужно добавить на отрезок <tex>[L_i,R_i]</tex>. Это делается аналогично тому, как в дереве отрезков происходит добавление на отрезке (процесс описан в статье "[[Несогласованные поддеревья. Реализация массового обновления]]"), но без <tex>push</tex>: нужно спуститься по дереву от корня и записать пару <tex>u_i,v_i</tex> в вершины дерева отрезков.
 +
 
 +
Теперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
 +
 
 +
=== Ответы на запросы ===
 +
Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить граф к состоянию, которое было при входе. Когда мы добираемся до листа, в граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.
  
Будем использовать систему непересекающихся множеств. Обойдём дерево отрезков в глубину, начиная с корня. При входе в вершину добавим в СНМ рёбра, записанные в этой вершине. При выходе из вершины нужно откатить СНМ к состоянию, которое было при входе (об этом ниже). Когда мы добираемся до листа, в СНМ уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.
+
Для поддержания такого графа и ответа на запросы будем использовать [[СНМ (реализация с помощью леса корневых деревьев)|систему непересекающихся множеств]]. При добавлении рёбер в граф объединим соответствующие множества в СНМ. Откатывание состояния СНМ описано ниже.
  
 
=== СНМ с откатами ===
 
=== СНМ с откатами ===
Как откатывать состояние СНМ? Каждый раз, когда мы изменяем что-то в СНМ, будем записывать в специальный массив, что именно мы изменили и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).
+
Для того, чтобы иметь возможность откатывать состояние СНМ, нужно при каждом изменении любого значения в СНМ записывать в специальный массив, что именно изменилось и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).
  
 
Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.
 
Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.
  
 
Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за <tex>O(\log n)</tex> на запрос истинно.
 
Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за <tex>O(\log n)</tex> на запрос истинно.
 +
 +
Запоминание изменений и откаты не влияют на время работы, если оно истинное, а не амортизированное. Действительно: пусть в СНМ произошло <tex>r</tex> изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за <tex>\Theta(r)</tex>. Но и сами изменения заняли <tex>\Theta(r)</tex> времени, значит, откаты не увеличили асимптотическое время работы.
 +
 +
Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность. <!-- Я не уверен, бывает ли персистентный СНМ, работающий за log. -->
  
 
== Время работы ==
 
== Время работы ==
Каждое из <tex>O(m)</tex> рёбер записывается в <tex>O(\log m)</tex> вершин дерева отрезков. Поэтому операций <tex>union</tex> в СНМ будет <tex>O(m \log m)</tex>. Каждая выполняется за <tex>O(\log n)</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> (СНМ с ранговой эвристикой). Откаты не влияют на время работы.
  
Можно считать, что <tex>n = O(\log m)</tex>, так как в запросах используется не более <tex>2m</tex> вершин.
+
Можно считать, что <tex>n = O(m)</tex>, так как в запросах используется не более <tex>2m</tex> вершин.
  
Время работы: <tex>O(m \log m \log n) = O(m \log^2 m)</tex>.  
+
Время работы: <tex>O(m \log m \log n) = O(m \log^2 m)</tex>.
  
 
== Реализация на C++ ==
 
== Реализация на C++ ==
Строка 200: Строка 208:
 
* Эту идею можно использовать и для других задач. Вместо СНМ можно использовать любую структуру данных, в которую можно добавлять, но не удалять.
 
* Эту идею можно использовать и для других задач. Вместо СНМ можно использовать любую структуру данных, в которую можно добавлять, но не удалять.
 
** Например, динамический рюкзак: добавлять предмет в него можно за <tex>O(w)</tex> (<tex>w</tex> {{---}} максимальный вес), а удалять нельзя. Аналогично тому, как в dynamic connectivity offline добавляются и удаляются рёбра, можно удалять элементы из рюкзака.
 
** Например, динамический рюкзак: добавлять предмет в него можно за <tex>O(w)</tex> (<tex>w</tex> {{---}} максимальный вес), а удалять нельзя. Аналогично тому, как в dynamic connectivity offline добавляются и удаляются рёбра, можно удалять элементы из рюкзака.
 +
 +
== См. также ==
 +
* [[СНМ (реализация с помощью леса корневых деревьев)|Система непересекающихся множеств]]
 +
* [[Дерево отрезков. Построение|Дерево отрезков]]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Связность в графах]]

Версия 11:05, 12 февраля 2020

Задача:
Имеется неориентированный граф из [math]n[/math] вершин, изначально не содержащий рёбер. Требуется обработать [math]m[/math] запросов трёх типов:
  • добавить ребро между вершинами [math]u[/math] и [math]v[/math],
  • удалить ребро между вершинами [math]u[/math] и [math]v[/math],
  • проверить, лежат ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности.
В графе могут быть кратные рёбра и петли.

В этой статье приведено решение задачи в offline, то есть ответы на все запросы будут получены после обработки всех запросов, а не по мере их поступления.

Решение упрощённой задачи

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

Время работы такого решения: [math]O(m \cdot \alpha (n))[/math], где [math]\alpha[/math]обратная функция Аккермана.

Алгоритм

Построение дерева отрезков

Рассмотрим массив запросов. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.

Пусть есть [math]k[/math] рёбер, [math]i[/math]-е соединяет вершины [math]v_i[/math] и [math]u_i[/math], было добавлено запросом [math]L_i[/math] и удалено запросом [math]R_i[/math].

Построим на массиве запросов дерево отрезков, в каждой его вершине будем хранить список пар. [math]i[/math]-е рёбро графа нужно добавить на отрезок [math][L_i,R_i][/math]. Это делается аналогично тому, как в дереве отрезков происходит добавление на отрезке (процесс описан в статье "Несогласованные поддеревья. Реализация массового обновления"), но без [math]push[/math]: нужно спуститься по дереву от корня и записать пару [math]u_i,v_i[/math] в вершины дерева отрезков.

Теперь чтобы узнать, какие рёбра существуют во время выполнения [math]i[/math]-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу — рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.

Ответы на запросы

Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить граф к состоянию, которое было при входе. Когда мы добираемся до листа, в граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.

Для поддержания такого графа и ответа на запросы будем использовать систему непересекающихся множеств. При добавлении рёбер в граф объединим соответствующие множества в СНМ. Откатывание состояния СНМ описано ниже.

СНМ с откатами

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

Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.

Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за [math]O(\log n)[/math] на запрос истинно.

Запоминание изменений и откаты не влияют на время работы, если оно истинное, а не амортизированное. Действительно: пусть в СНМ произошло [math]r[/math] изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за [math]\Theta(r)[/math]. Но и сами изменения заняли [math]\Theta(r)[/math] времени, значит, откаты не увеличили асимптотическое время работы.

Вместо описанного способа откатывания состояния СНМ можно использовать персистентный СНМ, но этот вариант сложнее и имеет меньшую эффективность.

Время работы

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

Можно считать, что [math]n = O(m)[/math], так как в запросах используется не более [math]2m[/math] вершин.

Время работы: [math]O(m \log m \log n) = O(m \log^2 m)[/math].

Реализация на C++

#include <bits/stdc++.h>

using namespace std;
typedef pair < int , int > ipair;
const int N = 100321;

// СНМ
int dsuP[N], dsuR[N];
// В этот массив записываются все изменения СНМ, чтобы их можно откатить
// При изменении какого-то значения в СНМ в hist записывается пара < указатель, старое значение >
vector < pair < int*, int > > hist;

// Для элемента из СНМ возвращает корень дерева, в котором он находится
int dsuRoot(int v)
{
    while (dsuP[v] != -1)
        v = dsuP[v];
    return v;
}

// Объединяет два множества. Используется ранговая эвристика.
// При любом изменении содержимого массивов dsuP и dsuR
// в hist записывается адрес и старое значение
void dsuMerge(int a, int b)
{
    a = dsuRoot(a);
    b = dsuRoot(b);
    if (a == b)
        return;
    if (dsuR[a] > dsuR[b])
    {
        hist.emplace_back(&dsuP[b], dsuP[b]);
        dsuP[b] = a;
    } else if (dsuR[a] < dsuR[b])
    {
        hist.emplace_back(&dsuP[a], dsuP[a]);
        dsuP[a] = b;
    } else
    {
        hist.emplace_back(&dsuP[a], dsuP[a]);
        hist.emplace_back(&dsuR[b], dsuR[b]);
        dsuP[a] = b;
        ++dsuR[b];
    }
}

struct Query
{
    int t, u, v;
    bool answer;
};
int n, m;
Query q[N];

// Дерево отрезков, в каждой вершине которого хранится список рёбер
vector < ipair > t[N*4];

// Эта функция добавляет ребро на отрезок
// [l r] - отрезок, на который добавляется ребро
// uv - ребро, c - текущая вершина дерева отрезков,
// [cl cr] - отрезок текущей вершины дерева отрезков
void addEdge(int l, int r, ipair uv, int c, int cl, int cr)
{
    if (l > cr || r < cl)
        return;
    if (l <= cl && cr <= r)
    {
        t[c].push_back(uv);
        return;
    }
    int mid = (cl + cr) / 2;
    addEdge(l, r, uv, c*2+1, cl, mid);
    addEdge(l, r, uv, c*2+2, mid+1, cr);
}

// Обход дерева отрезков в глубину
void go(int c, int cl, int cr)
{
    int startSize = hist.size();
    // Добавляем рёбра при входе в вершину
    for (ipair uv : t[c])
        dsuMerge(uv.first, uv.second);

    if (cl == cr)
    {
        // Если эта вершина - лист, то отвечаем на запрос
        if (q[cl].t == 3)
            q[cl].answer = (dsuRoot(q[cl].u) == dsuRoot(q[cl].v));
    } else {
        int mid = (cl + cr) / 2;
        go(c*2+1, cl, mid);
        go(c*2+2, mid+1, cr);
    }

    // Откатываем изменения СНМ
    while ((int)hist.size() > startSize)
    {
        *hist.back().first = hist.back().second;
        hist.pop_back();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    // Формат входных данных:
    // n и m, затем в m строках запросы: по три числа t, u, v
    // t - тип (1 - добавить ребро, 2 - удалить, 3 - принадлежат ли одной компоненте)
    // Нумерация вершин с нуля
    cin >> n >> m;
    for (int i = 0; i < n; ++i) // Инициализация СНМ
        dsuP[i] = -1;
    
    // В этом массиве для каждого ещё не удалённого ребра хранится
    // на каком запросе оно было создано
    set < pair < ipair, int > > edges;
    for (int i = 0; i < m; ++i)
    {
        cin >> q[i].t >> q[i].u >> q[i].v;
        // Поскольку рёбра неориентированные, u v должно означать то же самое, что и v u
        if (q[i].u > q[i].v) swap(q[i].u, q[i].v);
        // При добавлении ребра кладём его в set
        if (q[i].t == 1)
            edges.emplace(ipair(q[i].u, q[i].v), i);
        // При удалении ребра берём из set время его добавления - так мы узнаём отрезок заросов,
        // на котором оно существует. Если есть несколько одинаковых рёбер, можно брать любое.
        else if (q[i].t == 2)
        {
            auto iter = edges.lower_bound(make_pair(ipair(q[i].u, q[i].v), 0));
            addEdge(iter->second, i, iter->first, 0, 0, m - 1);
            edges.erase(iter);
        }
    }
    // Обрабатываем рёбра, которые не были удалены
    for (auto e : edges)
        addEdge(e.second, m - 1, e.first, 0, 0, m - 1);
    
    // Запускаем dfs по дереву отрезков
    go(0, 0, m - 1);
    // Выводим ответ.
    // При обходе дерева отрезков запросы обрабатываются в том же порядке, в котором они даны,
    // поэтому ответ можно выводить прямо в go без заполнения answer
    for (int i = 0; i < m; ++i)
        if (q[i].t == 3)
        {
            if (q[i].answer)
                cout << "YES\n";
            else
                cout << "NO\n";
        }

    return 0;
}

Замечания

  • Дерево отрезков можно строить не на всех запросах, а только на запросах третьего типа. Это даст выигрыш по скорости и памяти, особенно если таких запросов немного по сравнению с общим числом запросов.
  • Помимо проверки, лежат ли две вершины в одной компоненте связности, можно получать и другую информацию, которую можно получить из СНМ, напрмер:
    • Размер компоненты связности, которая содержит вершину [math]v[/math]
    • Количество компонент связности
  • Эту идею можно использовать и для других задач. Вместо СНМ можно использовать любую структуру данных, в которую можно добавлять, но не удалять.
    • Например, динамический рюкзак: добавлять предмет в него можно за [math]O(w)[/math] ([math]w[/math] — максимальный вес), а удалять нельзя. Аналогично тому, как в dynamic connectivity offline добавляются и удаляются рёбра, можно удалять элементы из рюкзака.

См. также