У меня есть запись, описывающая граф как набор узлов и ребер: data MyGraph a = MyGraph { nodes :: Set a, edges :: Set (a,a), components :: UnionFindM a -- ? } emptyGraph = MyGraph{ nodes = empty, edges = empty, components =...

Существует ли какой-либо усовершенствованный алгоритм непересекающихся множеств для действительно больших данных (например, более 2^32 элементов и более 2^32 пар для объединения)? Очевидно, самая большая проблема заключается в том, что я не могу...

Может ли кто-нибудь проверить со мной, использую ли я правило прямо на последнем шаге (7)? ОБНОВИТЬ: Числа в скобках — количество элементов (вес(?)) каждого набора, участвующего в объединении. Заглавные буквы — это названия наборов. Как я...

Я пытаюсь выполнить это упражнение во Введении в алгоритмы Кормена и др., которое связано со структурой данных Disjoin Set: Предположим, что мы хотим добавить операцию PRINT-SET(x) , которая получает узел x и печатает все элементы набора x...

Вопрос: http://codeforces.com/contest/468/problem/B Маленький X имеет n различных целых чисел: p1, p2, ..., pn. Он хочет разделить их все на два множества А и В. Должны быть выполнены следующие два условия: Если число x принадлежит множеству...

Я работаю над поиском профсоюза. Я хочу сгруппировать пары чисел на основе того, разделяет ли один из индексов число с индексом другой пары. Так: У меня есть массив таких пар: pairs: [[1,3], [6,8], [3,8], [2,7]] как лучше всего...

Итак, везде, где я вижу взвешенный алгоритм поиска объединения, они используют этот подход: Поддерживать массив, указывающий на родительский узел определенного узла Поддерживать массив, обозначающий размер дерева, в котором находится узел Для...

Я пытался реализовать алгоритм минимального сокращения Каргера так же, как это объясняется здесь , но мне не нравится тот факт, что на каждом шаге цикла while мы можем выбрать ребро с двумя конечными точками, уже находящимися в суперузле. Точнее,...