---
title: "Система непересекающихся множеств"
url: https://algopath.pro/ru/patterns/union-find
language: ru
summary: "Каждый элемент указывает на родителя, а подъём наверх приводит к корню, который называет группу. Элементы вместе, если корни совпали."
updated: 2026-08-24
---

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

Каждый элемент указывает на родителя, а подъём наверх приводит к корню, который называет группу. Элементы вместе, если корни совпали.

## Система непересекающихся множеств: как это работает?

Каждый элемент начинается своей группой. Его указатель ведёт на себя.

find поднимается по цепочке родителей до корня. Корень и есть имя группы.

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

Сжатие пути переписывает узлы на пути прямо на корень. Следующий find делает один шаг.

Ранговое объединение вешает низкое дерево под высокое. Так цепочки не растут.

С обоими приёмами find и union стоят почти константу. Рёбра при этом нигде не хранятся.

- `[0, 1, 2, 3, 4]` Пять элементов, пять групп. Каждый сам себе родитель.
- `[0, 0, 2, 3, 4]` union(0, 1) вешает 1 под 0. У двух элементов общий корень.
- `[0, 0, 2, 2, 4]` union(2, 3) вешает 3 под 2. Появилась вторая группа.
- `[0, 0, 0, 2, 4]` union(1, 2) находит корни 0 и 2. Корень 2 уходит под корень 0.
- `[0, 0, 0, 0, 4]` find(3) идёт 3, 2, 0. Сжатие ставит 3 сразу на 0.

## Система непересекающихся множеств: когда применять?

- лежат ли эти двое в одной группе
- факты о слиянии приходят по одному
- связность меняется по мере добавления рёбер
- склейка аккаунтов или друзей во времени
- это ребро замкнёт цикл

## Система непересекающихся множеств: с чем путают?

- **Компоненты связности** - Заливка считает группы в уже готовом графе. Здесь ответ нужен, пока рёбра ещё приходят.
- **Обход графа в ширину и глубину** - Обход ходит по соседям, значит нужен список смежности. Здесь рёбра не хранятся совсем.
- **Топологическая сортировка** - Топологический порядок требует направленных рёбер без циклов. Здесь любое ребро ненаправленное.
- **Хеш-таблица и множество** - Словарь группирует по заранее известному ключу. Здесь группы выясняются по мере слияний.

## Система непересекающихся множеств: сложность по времени и памяти

n до 1e6 элементов и m перемешанных запросов дают O(m alpha(n)). Alpha меньше 5 при любом реальном n.

## Система непересекающихся множеств: разбор примера

### Лишнее ребро

Дан граф, который был деревом, плюс одно лишнее ребро. Найдите ребро, замыкающее цикл.

Рёбра приходят по порядку. Верните последнее, соединяющее уже связанные вершины.

Идите по рёбрам подряд и объединяйте концы.

Если у концов уже общий корень, ребро ничего не добавляет. Оно замыкает цикл.

Запоминайте последнее такое ребро. Это и есть ответ.

```javascript
function findRedundantConnection(edges) {
    const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);

    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    let answer = [];
    for (const [a, b] of edges) {
        const rootA = find(a);
        const rootB = find(b);
        if (rootA === rootB) {
            answer = [a, b]; // both ends were already connected
        } else {
            parent[rootA] = rootB;
        }
    }

    return answer;
}
```

## Система непересекающихся множеств: частые ошибки

- **Сравнивают элементы, а не корни** Два элемента одной группы могут иметь разных родителей. Сравнивайте find(a) и find(b).
- **union без find** Запись parent[a] = b соединяет два элемента, а не две группы. Вешайте всегда корень под корень.
- **Пропускают сжатие пути** Без него цепочка вырастает до n звеньев. Один find тогда стоит O(n).
- **Размер массива берут по числу рёбер** Массив индексируется элементами, а не рёбрами. Ошибка на единицу даёт undefined на последней вершине.

## Система непересекающихся множеств: задачи с собеседований

- **Число провинций** Объедините все связанные пары и посчитайте разные корни.
- **Лишнее ребро** Первое ребро, у концов которого уже общий корень.
- **Слияние аккаунтов** Почты связывают аккаунты. Объединяйте по общей почте, потом группируйте по корню.
- **Число островов** Объединяйте соседние клетки суши. Удобно, когда сетка приходит частями.
- **Максимум убранных камней** Камни в одной строке или колонке образуют группу.
- **Выполнимость равенств** Сначала объедините равенства. Потом проверьте каждое неравенство по корням.
- **Наименьшая строка обменами** Обмениваемые индексы образуют группу. Отсортируйте буквы внутри каждой группы.

## JavaScript

```javascript
class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        const rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
        else { this.parent[ry] = rx; this.rank[rx]++; }
        return true;
    }
}
```

## Python

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True
```

## PHP

```php
class UnionFind {
    private array $parent;
    private array $rank;

    public function __construct(int $n) {
        $this->parent = range(0, $n - 1);
        $this->rank = array_fill(0, $n, 0);
    }

    public function find(int $x): int {
        if ($this->parent[$x] !== $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union(int $x, int $y): bool {
        [$rx, $ry] = [$this->find($x), $this->find($y)];
        if ($rx === $ry) return false;
        if ($this->rank[$rx] < $this->rank[$ry]) [$rx, $ry] = [$ry, $rx];
        $this->parent[$ry] = $rx;
        if ($this->rank[$rx] === $this->rank[$ry]) $this->rank[$rx]++;
        return true;
    }
}
```