Семейство непересекающихся множеств

Задача и применение

Дано множество \(E = \{x_i\colon i < n\}\) — Универсум.

В каждый момент времени существует разбиение

такое, что

Задача и применение

Задача и применение

Находит применение в решении задач

• построение минимального остова (алгоритм Краскала);
• Offline LCA (алгоритм Таржина);
• геометрический поиск;
• построение графов и деревьев;

Ранговая эвристика

Будем хранить компоненты связанности в виде деревьев. На них определим операцию \(\mathrm{GetRoot}(x)\), возвращающую корень дерева, в котором содержится \(x\).

Для каждой вершины поставим в соответствие её родителя \(\mathrm{Parent}(x)\). Для корней родитель не определён (\(\varnothing\)).

Ранговая эвристика

Как выбрать корень нового дерева?

Ранговая эвристика

Для каждого дерева определим ранг как высота этого дерева минус 1

Тогда в качестве нового корня выберем дерево с большим рангом.

Ранговая эвристика

Ранговая эвристика

1. \(r({x}) = 0\), \(w({x}) = 1\).
2. Пусть \(X\) и \(Y\) такие, что \(w(X) \geqslant 2^{r(X)}\) и \(w(Y) \geqslant 2^{r(Y)}\).

3. • Если \(r(X) < r(Y)\), тогда \(r(X \cup Y) = r(X)\), следовательно \(w(X \cup Y) \geqslant 2^{r(X, Y)}\).

   • Если \(r(X) = r(Y)\), тогда

Ранговая эвристика

Можно не запоминать ранги, используя вместо них рандомизацию. Получим рандомизированный логарифм.

Сжатие путей

После применения операции \(\mathrm{GetRoot}(x)\) выполним операцию \(\mathrm{Squash}(x, root)\).

def squash(x, root):
    p = x.parent
    if p != root:
        x.parent = root
        return squash(p, root)

Сжатие путей

Статистики

• количество / сумма;
• максимум / минимум;
• цвет / класс;

Статистики

Храниться только в корнях.

Важно задать правила по которым будет определяться статистика после слияния.

Динамический направленный лес

Лес с двумя операциями:

• \(\mathrm{GetRoot}(x)\) — будем хранить корень как статистику;
• \(\mathrm{AddEdge}(x, y)\) — разрешено, если \(y\) является корнем и \(\mathrm{GetRoot}(x) \neq \mathrm{GetRoot}(y)\).

Вариант реализации

Массив с индексами родителей.

Для корней можно хранить отрицательное число, в котором кодировать ранг или статистику.

Также можно добавлять новые элементы.