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

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

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

Реализации

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

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

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

Псевдокод:

int s[n]
init():
    for i = 0 to s.size - 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 s.size - 1:
            if s[i] == t:
                s[i] = s[x]

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

Пусть каждое множество хранится в виде списка. Вначале создается n списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на родительский элемент(parent) и ссылку на хвост(tail). Тогда для объединения множеств надо будет просто перекинуть ссылку parent на хвост другого множества. Таким образом, union работает за O(1).

Для того, чтобы найти элемент в одном из множеств, надо идти по parent'ам, пока он не указывает на Null - тогда мы нашли элемент-представитель. Таким образом, find работает за O(n).

Псевдокод:

list s[n]
init():
    for i = 0 to n - 1:
        s[i].set = i
        s[i].parent = Null
        s[i].tail = s[i]

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

union(x, y)://здесь важно, что x и y - представители множеств
    if x == y:
        return
    else:
        y.parent = x.tail
        x.tail = y.tail