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

Определение:

Система непересекающихся множеств (disjoint set union, DSU) — структура данных, поддерживающая операции [math]union(x, y)[/math] — объединения множеств, содержащих [math]x[/math] и [math]y[/math], и [math]find(k)[/math] — поиск множества, которому принадлежит элемент [math]k[/math].

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

Реализации

С помощью массива "цветов"

Оценка работы:

[math]init[/math]	[math]find[/math]	[math]union[/math]
[math]O(n)[/math]	[math]O(1)[/math]	[math]O(n)[/math]

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

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

Псевдокод:

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

find(k):
    return color[k]

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

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

Оценка работы:

[math]init[/math]	[math]find[/math]	[math]union[/math]
[math]O(n)[/math]	[math]O(n)[/math]	[math]O(1)[/math]

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

Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам [math]next[/math], пока он не указывает на [math]null[/math] — тогда мы нашли элемент-представитель. Таким образом, [math]find[/math] работает за [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 //сделали корректную ссылку на голову для представителя нового списка

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

Два списка до операции [math]union[/math]:

Два списка после операции [math]union[/math]:

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

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

Источники

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

Ссылки

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