---
title: "Система непересекающихся множеств: union-find за O(1) и когда его брать"
url: https://algopath.pro/ru/blog/sistema-neperesekayushchikhsya-mnozhestv
language: ru
summary: "Union-find отвечает, лежат ли два элемента в одной группе, почти за O(1). Массив parent, сжатие пути, код на Python и задача Number of Provinces."
updated: 2026-10-01
---

# Система непересекающихся множеств: 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 на цикле. Это частый следующий вопрос.

 

Отработать узнавание приёма среди соседних можно на странице [система непересекающихся множеств](/ru/patterns/union-find). Соседний приём разобран на странице [компоненты связности](/ru/patterns/graph-components).

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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