1679
правок
Изменения
м
Нет описания правки
{{Определение
| definition =
Система непересекающихся множеств(disjoint set union, DST) - структура данных, поддерживающая операции union(x, y) - объединения двух множеств , содержащих x и y , и find(k) - поиск множества, которому принадлежит элемент k.
}}
__TOC__
== Реализации ==
=== С помощью массива ===
Введем массив 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]
