СНМ (наивные реализации) — различия между версиями
(→С помощью списка) |
|||
| Строка 31: | Строка 31: | ||
=== С помощью списка === | === С помощью списка === | ||
| − | Пусть каждое множество хранится в виде списка. Вначале создается n списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на | + | Пусть каждое множество хранится в виде списка. Вначале создается n списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на следующий элемент(next) и ссылку на хвост(tail). Тогда для объединения множеств надо будет просто перекинуть ссылку next на начало другого множества. Таким образом, <tex> union </tex> работает за <tex> O(1) </tex>. |
| − | Для того, чтобы найти элемент в одном из множеств, надо идти по | + | Для того, чтобы найти элемент в одном из множеств, надо идти по next'ам, пока он не указывает на Null - тогда мы нашли элемент-представитель. Таким образом, <tex> find </tex> работает за <tex> O(n) </tex>. |
Псевдокод: | Псевдокод: | ||
| − | + | s[n] | |
init(): | init(): | ||
for i = 0 to n - 1: | for i = 0 to n - 1: | ||
s[i].set = i | s[i].set = i | ||
| − | s[i]. | + | s[i].next = Null |
s[i].tail = s[i] | s[i].tail = s[i] | ||
find(x)://подразумевается, что x - ссылка на один из элементов | find(x)://подразумевается, что x - ссылка на один из элементов | ||
| − | while x. | + | while x.next != Null: |
x = x.parent | x = x.parent | ||
return x.set | return x.set | ||
| Строка 52: | Строка 52: | ||
return | return | ||
else: | else: | ||
| − | y. | + | y.next = x.tail |
x.tail = y.tail | x.tail = y.tail | ||
Версия 06:22, 29 марта 2011
| Определение: |
| Система непересекающихся множеств(disjoint set union, DSU) - структура данных, поддерживающая операции - объединения множеств, содержащих x и y, и - поиск множества, которому принадлежит элемент k. |
Реализации
С помощью массива
Введем массив s, в будет храниться номер множества, к которому принадлежит i. Тогда , очевидно, будет работать за .
Чтобы объединить множества a и b, надо изменить все , равные a, на b. Тогда работает за .
Псевдокод:
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 списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на следующий элемент(next) и ссылку на хвост(tail). Тогда для объединения множеств надо будет просто перекинуть ссылку next на начало другого множества. Таким образом, работает за .
Для того, чтобы найти элемент в одном из множеств, надо идти по next'ам, пока он не указывает на Null - тогда мы нашли элемент-представитель. Таким образом, работает за .
Псевдокод:
s[n]
init():
for i = 0 to n - 1:
s[i].set = i
s[i].next = Null
s[i].tail = s[i]
find(x)://подразумевается, что x - ссылка на один из элементов
while x.next != Null:
x = x.parent
return x.set
union(x, y)://здесь важно, что x и y - представители множеств
if x == y:
return
else:
y.next = x.tail
x.tail = y.tail
Источники
- Т. Кормен - Алгоритмы, построение и анализ. Глава V-22.
