СНМ (наивные реализации) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами.  
 
'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами.  
 
__TOC__
 
__TOC__

Текущая версия на 19:28, 4 сентября 2022

Система (лес, объединение) непересекающихся множеств (СНМ, disjoint set forest, DSF, disjoint set union, DSU) — иерархическая структура данных, позволяющая эффективно работать с множествами.

Описание

Структура хранит набор объектов (например, чисел от [math] 0 [/math] до [math] n - 1 [/math]) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.

Определены две операции:

  • [math] \mathrm{union(x, y)} [/math] — объединяет множества, содержащие [math] x [/math] и [math] y [/math]
  • [math] \mathrm{find (x)} [/math] — возвращает представителя множества, в котором находится [math] x [/math]

Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов [math] x [/math] и [math] y [/math] одному множеству достаточно сравнить [math] \mathrm{find (x)} [/math] и [math] \mathrm{find(y)} [/math].

Пример работы СНМ

Реализации

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

Пусть в массиве s хранятся номера множеств, в [math] s[i] [/math] будет храниться номер множества, к которому принадлежит [math] i [/math]. Этот номер отождествляет множество, [math] \mathrm{find} [/math] возвращает именно его. Тогда [math] \mathrm{find} [/math], очевидно, будет работать за [math]O(1)[/math].

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

int s[n]
func init():
    for i = 0 to n - 1
        s[i] = i                // сначала каждый элемент лежит в своем множестве 
int find(k):
    return s[k]
func union(x, y):
    if s[x] == s[y]
        return
    else
        t = s[y]
        for i = 0 to n - 1
            if s[i] == t
                s[i] = s[x]

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

Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на [math] head [/math], который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на [math] head [/math]. Значит [math] \mathrm{find} [/math] работает за [math] O(1) [/math].

Для объединения множеств потребуется объединить два списка и обновить ссылки на [math] head [/math]. Таким образом, [math] \mathrm{union} [/math] работает за [math] O(n) [/math]. Чтобы объединить два списка, нужно хранить ссылку на [math] tail [/math]. Ее можно хранить в голове списка.

struct SetItem 
    int data       
    SetItem head
    SetItem next
    SetItem tail
SetItem s[n]
func init():
    for i = 0 to n - 1
        s[i].data = i
        s[i].head = s[i]         
        s[i].tail = s[i]
        s[i].next = null
int find(SetItem x):                         // подразумевается, что [math] x [/math] — ссылка на один из элементов 
    return x.head.data
func union(SetItem x, SetItem y):  // [math] x [/math] и [math] y [/math] — элементы множеств
    x = x.head
    y = y.head
    if x == y
        return
    x.tail.next = y                          // соединим списки 
    x.tail = y.tail                          // сделаем корректную ссылку на [math] tail [/math] в [math] head[/math]
    while y [math] \neq [/math] null                          // скорректируем ссылки на [math] head [/math] у элементов множества [math] y [/math] 
        y.head = x
        y = y.next
Пример объединения двух множеств (union)

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

Источники информации