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

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

Описание

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

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

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

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

Реализации

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

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

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

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$. Значит $\mathrm{find}$ работает за $O(1)$.

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

struct SetItem 
    int data       
    SetItem head
    SetItem next
    SetItem tail

SetItem s[n]

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

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

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

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

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

Источники информации

• Википедия — Система непересекающихся множеств
• Система непересекающихся множеств и её применения
• Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.