Dynamic-Connectivity Online
Что мы хотим получить?
- Все запросы в online
- Добавление ребра за O(log2n)
- Удаление ребра за O(log2n)
- Проверка, лежат ли две вершины в одной компоненте связности за O(logn)
Наивные решения
- Add = O(1), Del = O(1), Get = O(m)
- Add = DSU, Del = O(n+m), Get = DSU
Конструкция для правильного решения
- У каждого ребра есть ранг от 0 до log2n. При добавлении равен 0.
- Для каждого k = 0..log2n мы поддерживаем ET[k] − остовный лес на рёбрах с рангом 0..k
- В ET[k] размер каждой компоненты связности не более n / 2k. ET[0] − остов всего графа.
- Если ребро присутствует в остове ET[k], то оно присутствует и в ET[0]..ET[k-1].
- В ET[k] мы храним как Эйлеровы Обходы деревьев.
Хранение Эйлеровых обходов
- Храним для каждого ребра две ориентированных копии, для каждой вершины одну копию.
Построение: обойдём дерево, вершину выписываем при входе в неё, ребро при проходе по нему.
- Поддерживаем размер поддеревьев. Умеем делать split и merge.
- Умеем от вершины декартова дерева подняться до корня (храним родителей).
- Для каждого ребра знаем 2 вершины в каждом из log2n treap. Для каждой вершины знаем 1 вершину в каждом из log2n treap. Если такой вершины нет, храним 0.
Обработка запросов
- База: на каждом уровне каждая вершина лежит в своём декартовом дереве, состоящим только из этой вершины. Рёбер нет.
- Ответ на запрос
get(a, b)
: getRoot(vertexPosition[a, 0]) == getRoot(vertexPosition[b, 0])
- Запрос
add(a, b)
: if (!get(a, b)) { новое ребро = {a, b, rank=0}; makeRoot(a); makeRoot(b); merge(getRoot(a), новое ребро, getRoot(b), новое ребро) }
- Запрос
del(a, b)
: i = индекс ребра; if (edgePosition[i, rank[i]] == 0) return; for (j=0..rank[i]) { ET[j].splitByEdge(i); } найти замену!
Поиск ребра-замены-старого
- Ребро (a,b) ранга k разбило дерево на две компоненты. Возьмём из них за O(1) меньшую (мы знаем размер каждой).
- В меньшей из них все внутренние рёбра ранга k можно сделать ранга k+1
- И нужно найти хотя бы одно ребро наружу ранга не более k.
- Для этого научимся в ET[k] перебирать все рёбра ранга ровно k. И применим это к ET[j] в порядке j=k..0, пока не найдём ребро-замену-старому.
- В итоге мы переберём t + 1 ребро за время O(t + log2n). Так же мы для t из перебранных рёбер увеличим ранг.
Благодаря амортизации в сумме по всем запросом мы переберём не более m + nlog2n рёбер.
- Перебор рёбер нужного ранга: в treap кроме всего прочего мы храним количество вершин в поддереве,
которым соответствует вершина исходного графа, из которой есть исходящие рёбра нужного ранга.