Вопросы по теме 'disjoint-sets'
Алгоритм Прима с кучей Фибоначчи: почему O (E + V * log (V))?
Я знаю алгоритм Прима и как его реализовать. Я также знаю, почему его временная сложность равна O (E + V log (V)).
Мы добавляем ребра E раз (то есть за O (E)) и выбираем минимум V раз (то есть O (V * log (V)). Но я не понимаю части этого: почему V...
846 просмотров
schedule
29.10.2021
В Disjoint Set Union (D.S.U.), почему мы делаем подмножество меньшего размера дочерним по отношению к подмножеству большего размера при выполнении операции объединения?
Недавно я наткнулся на D.S.U. и его приложения на дереве. Когда я решал связанные проблемы, я получал ошибку Time Limit Exceeded в некоторых, поэтому я снова прочитал учебник и обнаружил, что импровизированная версия обычного объединения - это...
35 просмотров
schedule
12.11.2021
Тайм-аут поиска сотипов Freebase
Я пытаюсь найти сотипы freebase, то есть с учетом типа, который вы найдете «совместимыми» типами:
Предположим, начнем с /people/person, это может быть музыкант (/music/group_member), но не музыкальный альбом (/music/album), я не знаю, есть ли в...
89 просмотров
schedule
27.02.2022
Как обнаружить цикл в неориентированном графе с помощью непересекающихся множеств?
Алгоритм :
For each edge (u, v) in the Adjacency list:
If u and v do not belong to the same set:
Union(u, v)
else:
return true // cycle detected
return false
График :
(1)-------(2)
Список смежности :
[1] -> [2]
[2] -> [1]...
1058 просмотров
schedule
29.03.2022
Как я могу управлять освобождением памяти в непересекающихся наборах на С++?
У меня есть набор классов для обработки непересекающихся наборов в моем приложении C++. Мне трудно реализовать деструкторы для этих классов. Может ли кто-нибудь помочь мне в этом?
В основном они делают следующее: помещают указатели node s в...
320 просмотров
schedule
01.06.2022
Как правильно реализовать непересекающуюся структуру данных набора для поиска связующих лесов в Python?
Недавно я пытался внедрить решения вопросов по программированию Google Kickstater 2019 года и попытался реализовать Cherries Mesh Round E, следуя объяснению анализа. Вот ссылка на вопрос и анализ....
531 просмотров
schedule
23.06.2022
Как (эффективно) генерировать непересекающиеся наборы, используя пары элементов только один раз?
Что я хотел бы сделать, так это разделить группу из ( n ) элементов на группы одинакового размера (группы размера m , и для простоты Предположим, что остатков нет, т.е. n делится на m ). Выполняя это несколько раз , я хотел бы гарантировать,...
360 просмотров
schedule
24.06.2022
сжатия пути достаточно для непересекающихся лесов, зачем нам объединение по рангу
MAKE-SET(x）
x.p = x
x.rank = 0
UNION(x, y)
LINK(FIND-SET(x),FIND-SET(y))
LINK(x, y)
if x.rank > y.rank
y.p = x
else
x.p = y
if x.rand == y.rank
y.rank = y.rank +1
The FIND-SET procedure...
514 просмотров
schedule
16.07.2022
Непересекающиеся наборы структур данных и биномиальные деревья?
Может ли кто-нибудь объяснить, что такое структура данных непересекающихся множеств? Или, в качестве альтернативы, связать меня с видео или статьей на YouTube, которая хорошо это объясняет.
Я искал его несколько минут назад, и все, что я получил,...
1510 просмотров
schedule
26.07.2022
Проблема непересекающихся множеств
Я пытаюсь написать реализацию алгоритма Крускала с использованием непересекающихся наборов. Я думаю, что у меня это почти работает, но я не могу заставить часть кода работать правильно. Код должен проверить, находится ли узел на графе уже в наборе,...
1594 просмотров
schedule
29.07.2022
Докажите, что любой алгоритм решения непересекающихся множеств требует не менее nlog n
Проблема непересекающихся множеств
Пусть А и В два множества, они не пересекаются?
Вопрос
Докажите, что любой алгоритм решения непересекающихся множеств требует не менее O(nlog n) .
Идея, о которой я думал, состоит в том, чтобы...
164 просмотров
schedule
07.09.2022
набор вершинно-непересекающихся циклов, так что каждая вершина принадлежит циклу
Здесь у меня есть ориентированный граф G. Мне нужно определить, существует ли множество вершинно-непересекающихся циклов так, чтобы каждая вершина принадлежала циклу.
Я не уверен, можно ли это сделать за полиномиальное время или это NP-Complete?...
1202 просмотров
schedule
17.06.2023
Найдите количество непересекающихся множеств
Для тех, кто не знаком со структурой данных Disjoint-set.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Я пытаюсь найти нет. групп друзей из заданных наборов друзей и их взаимоотношений. Конечно, нет сомнений, что это можно легко...
5781 просмотров
schedule
08.11.2022
Как проверить, что все элементы списка не пересекаются?
Учитывая список нескольких итераций, я хочу проверить, все ли элементы не пересекаются .
два множества называются непересекающимися , если они не имеют общего элемента
Пример:
iterables = ["AB", "CDE", "AF"]
all_disjoint(iterables)
#...
1744 просмотров
schedule
14.04.2023
как на производительность алгоритма Краскала влияет структура данных непересекающегося набора?
У меня есть базовое представление о том, что такое алгоритм Краскала, и вот что я обнаружил:
Этот алгоритм в основном строит минимальное остовное дерево путем объединения нескольких деревьев и начинается с сортировки ребер по их весам. Начиная с...
741 просмотров
schedule
01.06.2023
Как сгенерировать наихудший случай для непересекающегося набора только с сжатием пути?
Непересекающийся набор с реализованным только сжатием пути выглядит следующим образом:
// In cpp.
int Find(int x) { return f[x] == x ? x : f[x] = Find(f[x]); }
int Union(int a, int b) { f[Find(a)] = Find(b); }
Из wiki я узнал о том, что...
163 просмотров
schedule
26.07.2023
Почему мой алгоритм Union Find Disjoint Sets для этой задачи не проходит все тесты?
Пример ввода:
1
3 2
1 2
2 3
Первая строка = количество тестовых случаев
Первая цифра второй строки = количество человек
Второе число второй строки = количество дружеских отношений, F
Следующие строки F = дружба
Результатом будет...
429 просмотров
schedule
19.07.2023
Как выбрать элементы в операции быстрого объединения?
Имеется набор элементов S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Здесь 10 элементов (N = 10). Массив arr для управления связностью элементов. Arr[ ], который индексируется элементами наборов размером N (как N элементов в наборе), используется для...
33 просмотров
schedule
13.02.2023
Как реализовать структуру данных union-find (непересекающийся набор) в Coq?
Я новичок в Coq, но для своего проекта мне приходится использовать структуру данных union-find в Coq. Существуют ли какие-либо реализации структуры данных union-find (непересекающийся набор) в Coq?
Если нет, может ли кто-нибудь предоставить...
119 просмотров
schedule
10.06.2023
