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

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

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

Реализации

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

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

Псевдокод:

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

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]
find(k):
    return s[k]