Конспект: непересекающиеся множества

Понятия

Система непересекающихся множеств (union-find) - три операции: make_set, find (представитель группы), union. Проверка «в одной ли группе» - это find(a) == find(b).

Лес представителей - parent[x] указывает на родителя, у корня parent[x] == x, корень и есть представитель группы. Списков членов группы структура не хранит и разъединять не умеет.

Объединение по рангу (размеру) - меньшее дерево подвешивают к большему; при равных рангах ранг нового корня растёт на единицу. Ранг - ВЕРХНЯЯ оценка высоты, после сжатия не пересчитывается.

Сжатие пути - find на обратном ходу перевешивает каждый узел пути прямо на корень. Есть однопроходный вариант (перевешивание на деда) с той же оценкой и меньшими константами.

α(n) - обратная функция Аккермана, растёт медленнее log*; α(n) <= 4 для любого записываемого n. «Почти константа», но не константа: нижняя граница Ω(m·α(n)) доказана.

Что унести

доказательство логарифма в одну строку:
ранг растёт только при слиянии РАВНЫХ → дерево ранга r держит ≥ 2^r узлов → r ≤ log₂ n

Обе оптимизации нужны вместе: каждая по отдельности даёт только O(log n).

Обнаружение «уже в одной группе» - не побочный эффект, а полезный ответ: в алгоритме Крускала именно он отбрасывает ребро, которое замкнуло бы цикл.

Принцип, общий у этой главы с предыдущей: не делай работу, которую можно отложить, и прибирайся там, куда всё равно пришёл. Массив меток обновляет представителя у всей группы сразу; лес переписывает одну ссылку и пересчитывает лениво, при следующем find, попутно сжимая путь. Тот же принцип - в ленивом удалении из очереди, в уплотнении кучи Фибоначчи, в удвоении динамического массива.

Где нельзя: связи должны только ДОБАВЛЯТЬСЯ. Удаление связей решают обращением времени или структурами динамической связности.

Куда это ведёт

Крускал (минимальное остовное дерево), компоненты связности, перколяция, разметка областей на изображении, унификация типов, оффлайновый поиск наименьшего общего предка. В Крускале union-find перестаёт быть узким местом вовсе: O(E·log E) там - это цена сортировки рёбер.