Описание тега disjoint-union
1
ответ
Как правильно реализовать операцию объединения в структуре данных с несвязными множествами?
Существует множество различных описаний и примеров структуры несвязных множеств, доступных в режиме онлайн. В некоторых случаях для каждого набора хранится "ранг". Когда набор объединяется в другой набор, ранг первого увеличивается на 1, если они им…
30 июл '17 в 04:32
1
ответ
Помеченные союзы в закрывающем компиляторе
В настоящее время я сравниваю компилятор Google Closure и статическую проверку типов Flow с точки зрения выразительности. Что мне нравится в последнем, так это то, что он, по-видимому, может довольно хорошо представлять помеченные союзы. Руководство…
15 дек '16 в 13:14
2
ответа
В поисках правильного объединения DST с обратно-аккерманной сложностью
Я говорю о структуре данных union-find-disjoint. В Интернете есть множество ресурсов о том, как это реализовать. До сих пор я узнал о двух методах оптимизации для профсоюзов. Первый - это "балансировка" дерева с помощью переменной Rank, которая гово…
12 апр '15 в 02:13
0
ответов
Money Matters uVA 11690 выдает "Неправильный ответ" и "Превышен лимит времени" после нескольких попыток
Вот ссылка на проблему: prob https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid;=8&page;=show_problem&problem;=2737 Следующее - моя реализация. Я попробовал их пример теста и несколько других, и все они дают правильные ответы. Но ко…
11 фев '16 в 15:43
2
ответа
O(1) Структура данных "Создать, найти, объединить в непересекающиеся множества"
Сегодня у меня была дискуссия с кем-то об алгоритме Kruskal Minimum Spanning Tree из-за страницы 13 этого слайда. Автор презентации сказал, что если мы реализуем непересекающиеся множества, используя (дважды) связанный список, производительность для…
14 авг '10 в 21:58
2
ответа
Disjoint Set Forest для планирования заданий
Как я могу использовать непересекающиеся наборы леса для планирования заданий с штрафами, чтобы штрафы были минимизированы? Мы могли бы сначала расположить рабочие места в порядке убывания на основе их штрафов. Каждый узел x леса будет представлять …
08 мар '13 в 07:24
0
ответов
Как рассчитать высоту непересекающихся деревьев, реализованных с помощью эвристического ранга?
Так как очень долго я пытаюсь решить вопрос из викторины, но я получаю неправильный ответ, вопрос заключается в следующем:- Consider the program: for i from 1 to 12: MakeSet(i) Union(2, 10) Union(7, 5) Union(6, 1) Union(3, 4) Union(5, 11) Union(7, 8…
09 фев '18 в 12:44
1
ответ
Несвязанный набор DS
Я изучал непересекающиеся наборы структур данных. У меня есть запрос, что при использовании объединения по рангу и сжатию путей вместе, если мы пропустим использование объединения по рангу и назначим приоритет (родительский) без сравнения рангов (ра…
22 июн '14 в 11:06
1
ответ
Соединение непересекающихся множеств в двумерном массиве
Я пытаюсь сгенерировать случайную сетку с позициями Traversable и Non-Traversable и убедиться, что есть путь от одной позиции Traversable к любой другой позиции Traversable в одном из 4 направлений {вправо, вверх, влево, вниз}. Проходные позиции пре…
10 апр '15 в 04:41
1
ответ
Получение максимального и минимального размера непересекающихся подмножеств
Я пишу код для выполнения Union-Find на графике, Первая строка ввода:nm [n - количество узлов, а m - количество ребер] Затем следуют m строк, указывающих, какие два узла связаны Когда я сталкиваюсь с каждым ребром, я выполняю операцию объединения, ч…
07 июн '16 в 16:32
0
ответов
Термин, описывающий объединение деревьев, которые разделяют листовые узлы
У меня есть структура данных, которая представляет собой объединение деревьев с одинаковым набором конечных узлов. Я думал, что это будет лес, но, очевидно, это относится к объединению несвязанных деревьев. Есть ли название для этой структуры?
21 июн '18 в 10:10
1
ответ
Доработка машинописного несвязного союза
Я пытаюсь заставить что-то вроде следующего работать, однако машинопись выдает ошибки при попытке доступа к o.foo имущество: type Base = { s: string }; type Extra = { foo: string; }; type Other = { bar: string; }; type T = Base & (Extra | Other)…
27 фев '19 в 14:53
1
ответ
Алгоритм поиска дизъюнктного объединения на графе зависимостей
Прежде всего, некоторый контекст о проблеме: Я работаю в системе, которая имеет несколько типов ресурсов (A, B, C...). Мне даны некоторые требования к ресурсам, и я должен определить, могу ли я их себе позволить. Для этого у меня есть несколько исто…
24 янв '13 в 00:13
1
ответ
Несвязанный Союз в LINQ
У меня есть два набора (ILists), где мне нужны все элементы из первого списка, где этот элемент не во втором списке. Кто-нибудь может указать мне на лучший способ достижения этого с помощью заявления LINQ?
29 апр '09 в 10:28
1
ответ
Какой подход лучше всего использовать Bfs, Dfs или Disjoint для поиска всех несвязных графов?
Какой подход мы должны использовать, чтобы найти все несвязные графы и почему? Как обходы BFS и DFS, так и методы обхода, и путем нескольких обходов. Мы можем найти все отключенные компоненты.И другим подходом может быть " Непересекающиеся множества…
18 окт '17 в 11:11
1
ответ
В Агде конструкторы не пересекаются? (или как опровергнуть травму)
Мне нужна еще одна лемма, показывающая, что inj₁ x ≡ inj₂ y абсурдно как часть большей теоремы о непересекающихся типах объединения (⊎ в Агде. Этот результат будет следовать непосредственно из двух конструкторов для ⊎ а именно inj₁ а также inj₂, буд…
31 янв '15 в 11:00
4
ответа
Леса с непересекающимися множествами - почему ранг должен быть увеличен на единицу, если находка двух узлов одного ранга?
Я реализую структуру данных с несвязным множеством, чтобы найти объединение. Я наткнулся на следующее утверждение в Википедии: ... если два дерева одного ранга r объединены, ранг результата равен r+1. Почему ранг соединенного дерева должен быть увел…
06 авг '13 в 13:24
1
ответ
Максимальный вес ребра от одного узла A до узла B
Дан связный неориентированный граф, имеющий N узлов (1 <= N <= 2 * 10 ^ 5) и N-1 ребер. Определим функцию F (a, b), где F (a, b) равен максимальному весу ребра на пути от a до b. Как нам найти сумму F (a, b) для всех a, b таких, что 1 <= a, b <= N (…
11 май '18 в 13:31
1
ответ
Самый быстрый способ объединить дубликаты ячеек без зацикливания Excel
У меня есть ячейки, содержащие повторяющиеся значения, которые я хочу быстро объединить. Таблица выглядит так: Sub MergeCells() Application.DisplayAlerts = False Dim n As Name Dim fc As FormatCondition Dim Rng As Range, R As Range Dim lRow As Long D…
17 авг '17 в 14:11
2
ответа
Эффективный поиск непустого пересечения (Java)
У меня есть метод, который возвращает целочисленное значение или целочисленный диапазон (initial..final), и я хочу знать, являются ли все значения непересекающимися. Есть ли более эффективное решение, чем следующее: ArrayList<Integer> list = n…
10 дек '12 в 16:56