Что такое Union Find / DSU?
На этой странице
Union Find, или DSU, - структура данных для работы с непересекающимися множествами. Она быстро отвечает, находятся ли элементы в одной группе, и быстро объединяет группы.
Вопрос
Что такое Union Find / Disjoint Set Union, зачем он нужен и как его реализовать?
Основная идея
Есть элементы:
0 1 2 3 4Сначала каждый элемент в своей группе:
{0} {1} {2} {3} {4}Потом делаем:
union(0, 1)
union(1, 2)Теперь:
{0, 1, 2} {3} {4}Запрос:
connected(0, 2) -> true
connected(0, 4) -> falseГде нужен DSU
- количество connected components;
- проверка, образует ли ребро цикл;
- Kruskal minimum spanning tree;
- accounts merge;
- redundant connection;
- dynamic connectivity;
- объединение групп пользователей/островов.
Базовая структура
DSU хранит:
parent[x]- родитель элемента;rankилиsize- высота/размер дерева для оптимизации.
class DSU {
private parent: number[]
private size: number[]
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, index) => index)
this.size = new Array(n).fill(1)
}
}Сначала каждый элемент родитель самому себе.
find
find(x) возвращает представителя группы.
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x])
}
return this.parent[x]
}Строка:
this.parent[x] = this.find(this.parent[x])делает path compression: после поиска элемент начинает ссылаться прямо на корень.
union
union(a, b) объединяет группы.
union(a: number, b: number): boolean {
let rootA = this.find(a)
let rootB = this.find(b)
if (rootA === rootB) {
return false
}
if (this.size[rootA] < this.size[rootB]) {
;[rootA, rootB] = [rootB, rootA]
}
this.parent[rootB] = rootA
this.size[rootA] += this.size[rootB]
return true
}Возвращаем false, если элементы уже были в одной группе. Это удобно для поиска лишнего ребра или цикла.
Полная реализация
class DSU {
private parent: number[]
private size: number[]
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, index) => index)
this.size = new Array(n).fill(1)
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x])
}
return this.parent[x]
}
union(a: number, b: number): boolean {
let rootA = this.find(a)
let rootB = this.find(b)
if (rootA === rootB) {
return false
}
if (this.size[rootA] < this.size[rootB]) {
;[rootA, rootB] = [rootB, rootA]
}
this.parent[rootB] = rootA
this.size[rootA] += this.size[rootB]
return true
}
connected(a: number, b: number): boolean {
return this.find(a) === this.find(b)
}
}Пример: количество компонент
function countComponents(n: number, edges: Array<[number, number]>): number {
const dsu = new DSU(n)
let components = n
for (const [a, b] of edges) {
if (dsu.union(a, b)) {
components--
}
}
return components
}Сложность
С path compression и union by size/rank операции почти константные:
find/union: амортизированно почти O(1)Формально часто пишут:
O(alpha(n))где alpha - обратная функция Аккермана, которая для практических размеров растет крайне медленно.
На собеседовании обычно достаточно сказать:
почти O(1) амортизированноDSU против DFS/BFS
DFS/BFS хороши, если граф статический и нужно один раз найти компоненты.
DSU хорош, если:
- ребра добавляются постепенно;
- много запросов
connected; - нужно быстро объединять группы;
- нужно проверять циклы при добавлении ребер.
Что важно помнить: частые ошибки
- Не делать path compression.
- Не использовать union by size/rank.
- Путать
parent[x]и root. - Уменьшать количество компонент даже если
unionвернулfalse. - Использовать DSU для directed graph задач, где нужны другие алгоритмы.
- Не преобразовать строковые id в числовые индексы.
Что отвечать на собеседовании?
DSU хранит разбиение элементов на непересекающиеся множества. find возвращает представителя множества, union объединяет два множества, connected проверяет общий корень. С path compression и union by size/rank операции работают почти за O(1) амортизированно. DSU полезен для connected components, cycle detection в undirected graph и Kruskal algorithm.
Мини-шпаргалка
- DSU = группы элементов.
find(x)- найти root.union(a, b)- объединить группы.connected(a, b)- один root или нет.- Path compression ускоряет
find. - Union by size/rank держит дерево низким.
- Хорош для undirected connectivity.