Union-Find: как работает и зачем нужен

Union-Find: структура данных, которую стоит знать

Вы когда-нибудь задумывались, как быстро проверить, есть ли связь между двумя узлами в графе, или объединить группы элементов? Union-Find (или DSU — disjoint set union) — это элегантное решение, которое пишется за пару минут, а его анализ производительности поражает воображение: время работы включает обратную функцию Аккермана. Звучит сложно, но на практике это одна из самых полезных структур для задач на графах, кластеризации и даже в социальных сетях. В этой статье мы разберём, как устроен Union-Find, какие оптимизации делают его быстрым, и где он применяется.

Представьте, что у вас есть набор элементов, и вы хотите объединять их в группы и быстро отвечать на вопрос «принадлежат ли два элемента одной группе?». Именно это и делает Union-Find. Визуально это можно представить как лес деревьев, где каждый элемент указывает на своего родителя, а корень дерева — представитель группы. Давайте разберёмся в деталях.

Три операции Union-Find: union, find, connected

Вся структура данных сводится к трём операциям:

• union(a, b) — объединяет группы, содержащие элементы a и b.
• find(a) — возвращает представителя (корень) группы, в которой находится a.
• connected(a, b) — проверяет, находятся ли a и b в одной группе, то есть find(a) === find(b).

Каждая группа представлена деревом: каждый узел указывает на своего родителя, а корень — на самого себя. Наивная реализация выглядит так:

parent = [0, 1, 2, 3, ...]  # каждый сам себе корень

def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

def union(a, b):
    parent[find(a)] = find(b)

Это работает, но если объединять группы бездумно, дерево может выродиться в связный список, и тогда find будет работать за O(n). К счастью, есть две оптимизации, которые решают эту проблему. Они показаны в интерактивной демонстрации, которую я создал: вы можете объединять группы, наблюдать за формированием деревьев и видеть, как сжатие пути сплющивает дерево в реальном времени.

▶ Живое демо: https://dev48v.github.io/union-find/
Исходный код: https://github.com/dev48v/union-find

Оптимизация 1: объединение по размеру (union by size)

Суть оптимизации проста: всегда подвешивайте меньшее дерево под корень большего. Это предотвращает чрезмерный рост глубины деревьев.

def union(a, b):
    ra = find(a)
    rb = find(b)
    if ra == rb:
        return  # уже в одной группе
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra  # меньшее под большим
    size[ra] += size[rb]

Благодаря этому высота дерева остаётся O(log n). В демо вы можете наблюдать, как при объединении мелких групп они всегда присоединяются к корню более крупной, и дерево остаётся сбалансированным.

Оптимизация 2: сжатие пути (path compression)

Вторая оптимизация — сжатие пути. Когда вы вызываете find для узла, вы проходите по цепочке родителей до корня. Вместо того чтобы просто вернуть корень, вы можете перенаправить каждый узел на пути прямо на корень. Тогда следующий вызов find для этих узлов будет выполняться за O(1).

def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    # сжатие пути: перенаправляем все узлы на корень
    while parent[x] != root:
        nx = parent[x]
        parent[x] = root
        x = nx
    return root

В демо запустите find на глубоком узле — и вы увидите, как янтарный путь схлопывается, и все узлы начинают указывать прямо на корень. Структура буквально ускоряется с каждым запросом.

Почему время работы — это фокус

С обеими оптимизациями m операций над n элементами работают за O(m · α(n)), где α — обратная функция Аккермана. Для любого n, которое помещается в наблюдаемой вселенной, α(n) ≤ 4, так что на практике это константа, но технически это не O(1). Это один из немногих случаев, когда точная оценка сложности алгоритма такая экзотическая.

Интересно, что даже без сжатия пути, только с union by size, сложность уже O(log n) на операцию. А с обеими оптимизациями мы получаем почти константное время, что делает Union-Find невероятно эффективным для задач с миллионами элементов.

Где вы реально примените Union-Find

• Алгоритм Краскала для поиска минимального остовного дерева: добавляйте самое дешёвое ребро, которое не образует цикл; проверка «образует ли цикл» — это как раз connected(a, b).
• Обнаружение циклов в неориентированном графе.
• Компоненты связности — после всех объединений можно подсчитать количество различных корней.
• Перколяция / связность сети, заливка областей на изображении, проверка «один ли кластер» для аккаунтов или друзей.

Union-Find — это не просто теоретическая структура, а практический инструмент, который экономит часы работы и упрощает код.

Практический вывод: что делать прямо сейчас

Откройте редактор и реализуйте Union-Find с обеими оптимизациями на Python. Затем решите задачу на LeetCode, например, Number of Provinces или Redundant Connection. Убедитесь, что вы понимаете, как работает сжатие пути — это ключ к эффективности. Если хотите увидеть визуализацию, загляните в демо и поиграйте с ним. А если статья помогла вам разобраться, поставьте звезду репозиторию на GitHub: https://github.com/dev48v/union-find.