СНМ (наивные реализации)

Система (лес, объединение) непересекающихся множеств (СНМ, disjoint set forest, DSF, disjoint set union, DSU) — иерархическая структура данных, позволяющая эффективно работать с множествами.

Описание

Структура хранит набор объектов (например, чисел от [math] 0 [/math] до [math] n - 1 [/math]) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.

Определены две операции:

• [math] \mathrm{union(x, y)} [/math] — объединяет множества, содержащие [math] x [/math] и [math] y [/math]
• [math] \mathrm{find (x)} [/math] — возвращает представителя множества, в котором находится [math] x [/math]

Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов [math] x [/math] и [math] y [/math] одному множеству достаточно сравнить [math] \mathrm{find (x)} [/math] и [math] \mathrm{find(y)} [/math].

Пример работы СНМ

Реализации

С помощью массива

Пусть в массиве s хранятся номера множеств, в [math] s[i] [/math] будет храниться номер множества, к которому принадлежит [math] i [/math]. Этот номер отождествляет множество, [math] \mathrm{find} [/math] возвращает именно его. Тогда [math] \mathrm{find} [/math], очевидно, будет работать за [math]O(1)[/math].

Чтобы объединить множества [math] x [/math] и [math] y [/math], надо изменить все [math] s[i] [/math], равные номеру множества [math] x [/math], на номер [math] y [/math]. Тогда union работает за [math]O(n)[/math].

int s[n]
func init():
    for i = 0 to n - 1
        s[i] = i                // сначала каждый элемент лежит в своем множестве 

int find(k):
    return s[k]

func union(x, y):
    if s[x] == s[y]
        return
    else
        t = s[y]
        for i = 0 to n - 1
            if s[i] == t
                s[i] = s[x]

С помощью списка

Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на head, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на head. Значит find работает за [math] O(1) [/math].

Для объединения множеств потребуется объединить два списка и обновить ссылки на head. Таким образом, union работает за [math] O(n) [/math]. Чтобы объединить два списка, нужно хранить ссылку на tail. Ее можно хранить в голове списка.

s[n]
init():
    for i = 0 to n - 1:
        s[i].data = i
        s[i].next = null
        s[i].head = s[i]

find(x): // подразумевается, что x — ссылка на один из элементов
    return x.head.data

union(x, y): // x и y — элементы множеств
    x = x.head
    y = y.head
    if x == y:
        return
    // соединим списки
    x.tail.next = y
    // сделаем корректную ссылку на tail в head
    x.tail = y.tail
    // скорректируем ссылки на head у элементов множества "y"
    while y != null:
        y.head = x
        y = y.next

Пример объединения двух множеств (union)

Другие реализации

• СНМ (списки с весовой эвристикой)
• СНМ (реализация с помощью леса корневых деревьев)

Источники

• Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.

Ссылки

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