Система непересекающихся множеств: union-find за O(1) и когда его брать

Короткий ответ. Система непересекающихся множеств хранит элементы группами и отвечает на один вопрос: лежат ли два элемента в одной группе. Две операции, find и union, работают почти за O(1). Её берут в задачах про соединённые города, друзей и компоненты графа. Ниже устройство, код на Python и задача Number of Provinces.

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

Есть n элементов. Каждый лежит ровно в одной группе. Группы можно сливать, а разделять нельзя.

У каждой группы есть представитель. Это один из её элементов, его называют корнем. Два элемента в одной группе, если у них общий корень.

Английское название union-find. В русских статьях встречается сокращение СНМ. Всё это одно и то же.

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

Один массив parent. В parent[i] лежит родитель элемента i. Корень указывает сам на себя.

Группа выглядит как дерево. Чтобы узнать корень, идём по родителям вверх. Чтобы слить группы, подвешиваем корень одной под корень другой.

Приём	Что делает	Глубина дерева
Без ускорений	Подвешиваем как попало	До n, то есть O(n) на запрос
Сжатие пути	При find все узлы на пути переподвешиваем к корню	Почти константа в среднем
Объединение по рангу	Меньшее дерево под большее	Не больше log n
Оба приёма	Стандартная реализация	Обратная функция Аккермана, на практике O(1)

По каким словам в задаче узнать этот приём?

• «Соединены ли города», «сколько групп друзей», «число компонент».
• «Добавляем рёбра по одному и после каждого отвечаем на вопрос».
• «Найти ребро, которое создаёт цикл».
• «Минимальное остовное дерево», алгоритм Крускала.

Ключевой признак: рёбра только добавляются. Если рёбра ещё и удаляют, приём не подходит. Тогда нужен обход графа заново.

Как выглядит слияние на примере?

Пять элементов, parent = [0, 1, 2, 3, 4]. Каждый сам себе корень, групп пять.

union(0, 1): корни 0 и 1, подвешиваем 1 под 0. parent = [0, 0, 2, 3, 4], групп четыре. union(2, 3): parent = [0, 0, 2, 2, 4], групп три.

union(1, 3): find(1) даёт 0, find(3) даёт 2. Подвешиваем 2 под 0: parent = [0, 0, 0, 2, 4]. Групп две. Теперь find(3) идёт 3, 2, 0. Сжатие пути перепишет parent[3] в 0, и следующий запрос дойдёт за один шаг.

union(0, 3) вернёт False. Оба корня уже 0, слияния не было. Ровно так ловят лишнее ребро в задачах про циклы.

Как написать систему непересекающихся множеств на Python?

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.groups = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # сжатие пути
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False          # уже в одной группе
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.groups -= 1
        return True

Метод union возвращает False, если элементы уже были вместе. Так удобно ловить цикл: ребро между вершинами одной группы замыкает его.

Как решить Number of Provinces через этот приём?

Дана матрица n на n. Единица в клетке (i, j) значит, что города i и j соединены. Нужно число групп городов.

Создаём DSU на n элементов. Проходим по матрице. Для каждой единицы делаем union(i, j). Ответ лежит в поле groups.

Сложность O(n²) на проход по матрице. Сами операции почти бесплатны. Обход в глубину дал бы тот же результат, но union-find короче в коде.

Где система непересекающихся множеств выигрывает у обхода графа?

Обход в глубину считает компоненты за один проход. Если граф не меняется, этого достаточно.

Union-find выигрывает, когда рёбра приходят потоком. После каждого нового ребра ответ обновляется за O(1). Обход пришлось бы запускать заново, а это O(V + E) на каждый запрос.

На каких ошибках ломается решение?

• Сравнивают parent[a] и parent[b] вместо find(a) и find(b). Родитель это не корень.
• Забывают сжатие пути и получают деревья глубиной n.
• Считают группы отдельным проходом вместо счётчика в union.
• Индексируют города с единицы, а массив с нуля.

Как объяснить приём на собеседовании?

Скажите: нужно быстро отвечать «в одной ли группе», пока группы сливаются. Назовите две операции и массив parent. Упомяните сжатие пути и ранг, назовите почти константное время.

Потом покажите, что union возвращает False на цикле. Это частый следующий вопрос.

Отработать узнавание приёма среди соседних можно на странице система непересекающихся множеств. Соседний приём разобран на странице компоненты связности.

Вопросы и ответы

Можно ли удалить элемент из группы?

В базовой структуре нет. Нужен либо обход графа заново, либо обратный порядок: добавлять рёбра с конца.

Нужен ли ранг, если есть сжатие пути?

Сжатия пути одного хватает для задач на собеседовании. Ранг даёт строгую оценку log n на худший запрос. На практике пишут оба.

Как посчитать размер каждой группы?

Заведите массив size, в начале все единицы. При слиянии прибавляйте размер меньшего дерева к большему. Размер группы элемента x лежит в size[find(x)]. Тот же массив можно взять вместо ранга: подвешивать меньшую группу под большую.

Как хранить строки вместо чисел?

Заведите словарь строка в номер. Номера выдавайте по мере появления. Дальше работает та же структура.