Описание тега disjoint-sets
Все, что связано с непересекающимися множествами, то есть математическими множествами, у которых нет общих элементов.
3
ответа
Разрывать-устанавливать леса в альтернативной реализации Python
Я внедряю систему непересекающихся множеств в Python, но я попал в стену. Я использую древовидную реализацию для системы и реализую функции Find(), Merge() и Create() для системы. Я внедряю систему рангов и сжатие путей для эффективности. Уловка в т…
28 фев '12 в 19:20
1
ответ
Как правильно реализовать операцию объединения в структуре данных с несвязными множествами?
Существует множество различных описаний и примеров структуры несвязных множеств, доступных в режиме онлайн. В некоторых случаях для каждого набора хранится "ранг". Когда набор объединяется в другой набор, ранг первого увеличивается на 1, если они им…
30 июл '17 в 04:32
0
ответов
Stata: разделить упорядоченный по времени массив на непересекающиеся множества
Я ищу способ Stata разделить упорядоченный по времени массив на подмножества, которые не содержат перекрывающихся элементов / наблюдений. Пример: допустим, у меня есть переменная meal для каждого человека в день, и я хотел бы определить, когда челов…
27 фев '17 в 18:54
1
ответ
Как реализовать лабиринт, используя непересекающиеся множества?
Вот класс DisjointSet, который я использую: public class DisjointSet{ public DisjointSet(int size){ s = new int[size]; for(int i = 0; i < size; ++i){ s[i] = -1; } } public void union(int el1, int el2){ int root1 = find(el1); int root2 = find(el2)…
15 апр '15 в 20:32
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
0
ответов
Наивная функциональная реализация Union Find Disjoint Set имеет плохую производительность
Следующая реализация UFDS имеет низкую производительность. Может ли кто-нибудь объяснить мне, почему это может быть? Вот отчет по профилированию: total time = 0.10 secs (98 ticks @ 1000 us, 1 processor) total alloc = 78,869,168 bytes (excludes profi…
22 май '18 в 22:39
2
ответа
Как на производительность алгоритма Крускала влияет несвязанная структура данных набора?
У меня есть общее представление о том, что такое алгоритм Крускала, и вот что я обнаружил: Этот алгоритм в основном строит минимальное остовное дерево путем объединения нескольких деревьев, и он начинает с сортировки ребер по их весам. Начиная с пус…
17 авг '17 в 19:32
0
ответов
Несвязанные множества со связанным списком, C++ - Cormen
Это моя реализация Несвязных множеств в соответствии с Корменом (Введение в алгоритмы - 2-е изд., Глава 21).У меня проблемы при удалении объектов (деструктор "~DisjointSet").Это происходит потому, что регистры "std::vector sets;" может указывать на …
20 апр '14 в 22:25
1
ответ
Разделите граф на непересекающиеся множества одинакового размера с минимальным разрезом
Существует ли какой-либо алгоритм или код, который делит узлы графа на два или более непересекающихся множества, которые удовлетворяют следующим условиям: во-первых, удаляются только ребра. во-вторых, ребра взвешены, и те, которые будут удалены, дол…
09 окт '16 в 14:56
4
ответа
Эффективный алгоритм для определения, если два набора чисел не пересекаются
Практика для интервью разработчиков программного обеспечения и застрял на вопрос алгоритма. Given two sets of unsorted integers with array of length m and other of length n and where m < n find an efficient algorithm to determine if the sets are …
08 июл '14 в 19:41
0
ответов
Существует ли система БД, которая поддерживает структуру данных Union-Find (Disjoint Sets)
В основном ищет БД, которая поддерживает эту структуру данных OOTB
18 мар '18 в 11:18
0
ответов
Как сжатие пути в непересекающемся множестве может привести к O(log*n)
Я только что прочитал лекцию о некоторых структурах данных о непересекающихся множествах. я не могу найти достаточно хорошего объяснения о том, как сжатие пути может сделать find() алгоритм становится O(log* n). я читаю книгу "Алгоритм" С. Дасгупты …
04 май '18 в 09:41
2
ответа
Алгоритм объединения / поиска без объединения по рангу для структуры данных о лесах с непересекающимся множеством
Вот разбивка алгоритма объединения / поиска для непересекающихся наборов лесов в Википедии: Barebone непересекающиеся набор леса... (O(n)) ... с объединением по рангу... (теперь улучшено до O(log(n)) ... со сжатием пути (теперь улучшено до O(a(n))эф…
24 фев '10 в 02:53
1
ответ
В реализации Java алгоритма Крускала, где именно мы должны выполнить Path Compression?
При реализации алгоритма Крускала в Java с использованием наборов Disjoint следует ли называть сжатие пути отдельной функцией или она должна быть неотъемлемой частью функции find()?
30 дек '18 в 02:58
1
ответ
Почему ранг не равен высоте множества в непересекающемся множестве?
Недавно я читал о структуре данных disjoint-set-union. Я запутался насчет ранга эвристического. Я прочитал, что "ранг не высота дерева". Я не могу найти это требование правильно. Дело в том, что когда для объединения используется эвристика ранга, мы…
27 янв '19 в 21:00
0
ответов
Сократите список интервалов (время начала и окончания), чтобы получить максимальное количество непересекающихся функций, которые мы можем посетить за день
Я создаю программу на Java 8, которая дает максимальное количество функций, которые человек может посещать за день. т.е.) Человек может присутствовать только в одной функции в любой заданный интервал времени. Я попытался написать код, чтобы найти ре…
14 фев '19 в 07:36
1
ответ
Несвязанный Устанавливает ошибку времени сжатия пути
Сейчас я прохожу онлайн курс по структуре данных. Вот моя Python-реализация алгоритма слияния и поиска. Я следовал инструкциям, но время работы намного превышает пределы. Кто-нибудь может взглянуть? Это должно быть просто. Благодарю. Мы должны сдела…
31 авг '16 в 06:43
2
ответа
O(1) Структура данных "Создать, найти, объединить в непересекающиеся множества"
Сегодня у меня была дискуссия с кем-то об алгоритме Kruskal Minimum Spanning Tree из-за страницы 13 этого слайда. Автор презентации сказал, что если мы реализуем непересекающиеся множества, используя (дважды) связанный список, производительность для…
14 авг '10 в 21:58
2
ответа
Как (эффективно) генерировать непересекающиеся множества, используя пары элементов только один раз?
То, что я хотел бы сделать, это разделить группу (n) элементов на группы одинакового размера (группы размера m, и для простоты предположим, что остатков нет, т.е. n делится на m). Делая это несколько раз, я хотел бы убедиться, что ни одна пара предм…
26 сен '15 в 21:38
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