Что такое структура непересекающихся множеств (union-find) со сжатием пути и объединением по рангу?

Question

Accepted Answer

**Непересекающихся множеств** (union-find) отслеживает элементы, разделённые на непересекающихся группы, и отвечает на вопросы "**находятся ли эти двое в одной группе?**" и "**объединить две группы**" за **почти постоянное время**. С **сжатием пути** и **объединением по рангу** обе операции выполняются за **O(α(n))** — практически O(1) (α — обратная функция Аккермана).

## Как это работает

Каждое множество — это дерево; **корень** — представитель множества. `find` идёт к корню; `union` связывает один корень под другим.

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## Код

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        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
        return True
```

| Операция | Время (с обеими оптимизациями) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Частые применения

- **Минимальное остовное дерево Крускала** — объединять компоненты без образования циклов.
- **Связные компоненты** графа или сетки.
- **Динамическая связность** и задачи сетей/перколяции.

## Почему это важно

Union-find решает задачи группировки и связности, которые иначе требовали бы повторяющихся O(n) обходов графа, сводя их к почти O(1) за запрос.

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