Непересекающиеся множества: лес представителей

Если ты знаешь API union-find, понимаешь идею «представитель - это корень дерева» и видишь, во что вырождается наивный лес, листай до «Теперь сам».

Как думаешь, что здесь дорого

Пусть элементов миллион, а объединений - миллион. Прежде чем читать дальше, прикинь стоимость простейшего решения: держим массив метка[i] - номер группы элемента. Проверка «в одной ли группе» мгновенна: сравнить метки. А объединение? Придётся пройти весь массив и перекрасить все элементы одной группы в метку другой - O(n) на объединение, O(n²) на всё. Вопрос: где здесь лишняя работа и как её не делать?

На что это похоже

Компании и их владельцы. Чтобы узнать, принадлежат ли два магазина одной сети, не нужно переписывать вывески всех магазинов при каждом поглощении - достаточно у каждого знать, кому он подчиняется, и подняться по цепочке до САМОГО ВЕРХНЕГО владельца. Одинаковый владелец - одна сеть. А поглощение - это одна запись: владелец одной сети теперь подчиняется владельцу другой. Мгновенно, без обхода всех магазинов. Плата очевидна: если цепочка подчинения вытянулась в длинную нить, выяснение владельца становится долгим.

Механизм: лес, где представитель - это корень

parent[x]  - на кого указывает x; у корня parent[x] == x

make_set(x): parent[x] = x                  создать группу из одного элемента

find(x):     пока parent[x] != x: x = parent[x]
             вернуть x                      подняться до корня - это представитель

union(a, b): ra = find(a); rb = find(b)
             если ra != rb: parent[rb] = ra  подвесить один корень к другому

в одной ли группе(a, b):  find(a) == find(b)

Множество здесь - это дерево, а имя множества - его корень. Никаких списков элементов группы не хранится вовсе: структура умеет отвечать только на вопрос «одна ли группа», и именно поэтому она такая дешёвая. Перечислить всех членов группы она не может - для этого нужен ещё один проход по всем элементам.

Сравним два наивных подхода:

массив меток : find  O(1)          union O(n)   - перекрасить всю группу
лес (наивно) : find  O(глубины)    union O(глубины) - сам вызывает два find,
                                                     но переписывает лишь одну ссылку

Беда леса в том, что глубину никто не ограничивает. Объединяй по очереди union(1,0), union(2,1), union(3,2), ... - и каждый раз корень подвешивается к новому элементу, получая цепочку длиной n. find последнего элемента пройдёт всю цепочку - O(n), и никакой экономии по сравнению с метками не осталось.

Правило

Система непересекающихся множеств хранит группы как лес: parent[x] указывает на родителя, у корня parent[x] == x, и корень - ПРЕДСТАВИТЕЛЬ группы. find(x) поднимается до корня, union подвешивает один корень к другому, «в одной ли группе» - это find(a) == find(b). Структура отвечает только на вопрос о принадлежности одной группе и не умеет перечислять её элементы. Без дополнительных правил лес вырождается в цепочку, и find становится O(n).

Разбор: пять объединений по шагам

Элементы 0..5, каждый сам себе группа: parent = [0, 1, 2, 3, 4, 5].

1. union(0, 1): find(0) = 0, find(1) = 1, разные - parent[1] = 0. Состояние: [0, 0, 2, 3, 4, 5]. Групп стало 5.
2. union(1, 2): find(1) идёт 1 → 0, значит 0; find(2) = 2; подвешиваем: parent[2] = 0. Состояние: [0, 0, 0, 3, 4, 5]. Групп 4.
3. union(3, 4): корни 3 и 4, parent[4] = 3. Состояние: [0, 0, 0, 3, 3, 5]. Групп 3.
4. union(0, 2): find(0) = 0, find(2) идёт 2 → 0, значит 0. Корни СОВПАЛИ - объединять нечего, это «лишнее» объединение. Состояние не меняется, групп по-прежнему 3.
5. union(4, 5): find(4) идёт 4 → 3, значит 3; find(5) = 5; parent[5] = 3. Состояние: [0, 0, 0, 3, 3, 3]. Групп 2.

Итог: две группы {0,1,2} и {3,4,5}, одно объединение оказалось лишним. Обрати внимание на шаг 4: обнаружение «уже вместе» - не побочный эффект, а полезный ответ. Забегая вперёд: алгоритм Крускала (раздел про остовные деревья) перебирает связи сети от самой дешёвой к самой дорогой и берёт связь, только если её концы ещё в РАЗНЫХ группах; ответ «уже вместе» означает, что эта связь лишняя, и её пропускают.

Разбор: во что обходится наивность

Посчитаем на n = 200 элементах и 160 объединениях - ровно тот вход, который встретится в задаче.

Массив меток: каждое РЕЗУЛЬТАТИВНОЕ объединение перекрашивает элементы, проходя весь массив, - это 200 итераций. Из 160 рёбер результативными оказываются 154 (шесть соединяют уже связанные элементы), значит порядка 154 × 200 ≈ 31000 итераций внутреннего цикла. Замер на движке курса - там это ровно заготовка задачи в конце главы: 95 676 шагов.

Лес с рангом и сжатием путиРазбирается в разделе 9, глава «Непересекающиеся множества, ранг и сжатие пути»: Сжатие пути и почти константа (следующие два урока): find проходит единицы шагов, и всё решение укладывается в 4103 шага (тот же замер) - в двадцать три раза меньше. Причём разрыв растёт вместе с n: у меток он квадратичен по числу операций, у леса - почти линеен.

Заметь, что дело не в «плохой» структуре: массив меток отвечает на вопрос find мгновенно, лучше леса. Он проигрывает потому, что обновляет то, что можно НЕ обновлять: при объединении двух групп ответ меняется у всех членов одной из них, но узнать об этом им можно и позже, лениво, когда спросят. Лес именно это и делает - переписывает одну ссылку, а пересчёт откладывает до find.

Что ломается без этого

Первое: сравнивать сами элементы, а не их представителей, - «в одной группе» определяется ТОЛЬКО через find, метка родителя без подъёма до корня ничего не значит. Второе: в union подвешивать элементы вместо корней (parent[b] = a без find) - структура перестанет быть лесом деревьев с корнями, и группы перепутаются. Третье: ждать, что структура перечислит членов группы, - она этого не умеет, нужен отдельный проход или отдельный список. Четвёртое: разъединение. Union-find НЕ поддерживает split или откат в общем случае: объединения необратимы. Задачи, где связи ещё и УДАЛЯЮТСЯ, решают иначе - обращением времени (обрабатывают запросы в обратном порядке) или «динамической связностью» с куда более сложными структурами.

Зачем это в работе

Эта структура держит на себе алгоритм Крускала (минимальное остовное дерево), и там же видно, зачем нужны обе операции: find проверяет, не замкнёт ли ребро цикл, union добавляет ребро в остов. Кроме того: поиск компонент связности - групп элементов, соединённых прямо или через цепочку соседей (когда связи приходят по одной, это проще обхода), анализ перколяции и связности сетей, разметка связных областей на изображении, проверка эквивалентности в системах типов и в алгоритмах унификации, оффлайновый поиск наименьшего общего предка (алгоритм Тарьяна), группировка дубликатов при дедупликации. Общая примета задачи, в которой нужен union-find: связи только ДОБАВЛЯЮТСЯ, и вопрос всегда один - «это уже связано?».

Теперь сам

Элементы 0..6. Выполни по очереди: union(0,1), union(2,3), union(1,3), union(4,5), union(0,2), union(5,6). Сколько получится групп и сколько объединений окажутся лишними? Подвешивай всегда второй корень к первому.