Система непересекающихся множеств (Union-Find) со сжатием путей и объединением по рангу. find/union — почти O(1) (обратная функция Аккермана). Применяется для поиска компонент связности, алгоритма Краскала и т. п.
find
union
const ds = new DisjointSet(['a', 'b', 'c']);ds.union('a', 'b');ds.connected('a', 'b'); // trueds.setCount; // 2 Copy
const ds = new DisjointSet(['a', 'b', 'c']);ds.union('a', 'b');ds.connected('a', 'b'); // trueds.setCount; // 2
Количество элементов.
Количество непересекающихся множеств.
Добавляет элемент как отдельное множество. Возвращает false, если он уже есть.
false
Представитель множества, содержащего value; undefined, если элемента нет.
value
undefined
Объединяет множества, содержащие a и b. Отсутствующие элементы добавляются автоматически. Возвращает false, если они уже были в одном множестве.
a
b
Находятся ли a и b в одном множестве.
Все множества; каждое — массив элементов.
Система непересекающихся множеств (Union-Find) со сжатием путей и объединением по рангу.
find/union— почти O(1) (обратная функция Аккермана). Применяется для поиска компонент связности, алгоритма Краскала и т. п.Example