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

Описание

Система непересекающихся множеств (disjoint set union, DSU)

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

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

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

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

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

Реализации

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

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

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

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

find(k):
    return s[k]

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

Старая версия

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

Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам next, пока он не указывает на null — тогда мы нашли элемент-представитель. Таким образом, find работает за [math]O(n)[/math].

Псевдокод:

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

find(x): // подразумевается, что x — ссылка на один из элементов
    while x.next != null:
        x = x.next
    return x.set

union(x, y): // здесь важно, что x и y — представители множеств
    if x == y:
        return
    else:
        x.next = y.head // соединили списки
        y.head = x.head // сделали корректную ссылку на голову для представителя нового списка

Пример работы:

Два списка до операции union:

Два списка после операции union:

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

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

Источники

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

Ссылки

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