re:re:actable
Урок 084 минуты чтения

Что такое 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.

Документация

cp-algorithms: Disjoint Set Union.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам