Система непересекающихся множеств (DSU)
Система непересекающихся множеств: find и union со сжатием путей — почти O(1).
Задача: элементы объединяются в группы, и нужно быстро отвечать «в одной ли группе a и b?» и «объединить группы a и b». Наивно — медленно; DSU (Disjoint Set Union) делает обе операции почти за O(1).
Идея: каждая группа — дерево, представитель группы — корень. find(v) поднимается до корня; union подвешивает один корень к другому.
Две эвристики делают структуру молниеносной:
• сжатие путей: по дороге к корню перевешиваем все вершины сразу на корень;
• объединение по рангу: меньшее дерево подвешивается к большему.
DSU. Введите: 5 5, затем запросы: union 1 2 / union 3 4 / check 1 3 / union 2 3 / check 1 4
Запустите пример: после union 1 2 и union 3 4 вершины 1 и 3 в разных группах (NO), после union 2 3 — в одной (YES).
Строка parent[v] = find(parent[v]) — то самое сжатие пути: возвращаясь из рекурсии, все пройденные вершины подвешиваются прямо к корню. С обеими эвристиками амортизированная сложность — обратная функция Аккермана, на практике неотличимая от константы.
Где DSU стреляет: подсчёт компонент связности при добавлении рёбер, алгоритм Краскала для минимального остова (уровень 4), задачи «объединить и спросить».
Задание: добавьте в DSU подсчёт размера каждой группы (массив size, при объединении size[a] += size[b]) и отвечайте на запрос «сколько элементов в группе x».
Отметьте урок пройденным — Уровень 3 завершён, впереди графы!