disjoint-sets Questions
2
I trying to find algorithm of searching disjoint sets (connected components/union-find) on large amount of data with apache spark.
Problem is amount of data. Even Raw representation of graph vertex...
Soapberry asked 18/5, 2016 at 10:39
3
Solved
I would have expected such a useful data structure to be included in the C++ Standard Library but I can't seem to find it.
Shashaban asked 22/4, 2017 at 16:34
1
Solved
I am solving a problem on LeetCode:
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time. So...
Babism asked 12/3, 2022 at 22:11
5
Solved
I need to use boost::disjoint_sets, but the documentation is unclear to me. Can someone please explain what each template parameter means, and perhaps give a small example code for creating a disjo...
Kesselring asked 9/11, 2010 at 14:24
2
Solved
I am relatively new to Python. I am studying Disjoint sets, and implemented it as follows:
class DisjointSet:
def __init__(self, vertices, parent):
self.vertices = vertices
self.parent = parent...
Dysphonia asked 4/1, 2019 at 13:31
2
Solved
I have been reading about union-find problem. The two main improvements are path compression and union by rank. As far as I understand union by rank is used to determine how to combine disjoint tre...
Richers asked 16/1, 2017 at 23:43
2
Assume you have many elements, and you need to keep track of the equivalence relations between them. If element A is equivalent to element B, it is equivalent to all the other elements B is equival...
Ismaelisman asked 17/9, 2010 at 19:52
5
Solved
I am implementing the disjoint-set datastructure to do union find. I came across the following statement in Wikipedia:
... whenever two trees of the same rank r are united, the rank of the resul...
Kahle asked 6/8, 2013 at 13:24
1
Problem Statement:
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number).
Given some queries, return the...
Josefinejoseito asked 23/8, 2018 at 15:57
5
Solved
What I have so far is largely based off page 571 of "Introduction To Algorithms" by Cormen et al.
I have a Node class in python that represents a set:
class Node:
def __init__(self, parent, rank...
Missive asked 23/2, 2011 at 18:4
2
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 proce...
Chug asked 30/3, 2018 at 12:25
1
I didn't find any good implementation of Disjoint Set in C# using Union by rank implementation so I implemented my own. It works in O(log n) time complexity.
Is there faster (or built-in implemen...
Navicular asked 23/9, 2017 at 18:52
2
Solved
I need to randomly separate a data frame into two disjoint sets by the attribute 'ids'. For example, consider the following data frame:
df=
Out[470]:
0 1 2 3 ids
0 17.0 18.0 16.0 15.0 13.0
1 18....
Torpedoman asked 16/5, 2017 at 17:1
10
I am trying to implement Disjoint Sets for use in Kruskal's algorithm, but I am having trouble understanding exactly how it should be done and in particular, how to manage the forest of trees. Afte...
Vitiligo asked 21/12, 2010 at 11:38
2
Solved
What I would like to do is split a group of (n) items into groups of equal size (groups of size m, and for simplicity assume that there are no leftovers, i.e. n is divisible by m). Doing this multi...
Flour asked 26/9, 2015 at 21:38
2
Solved
For those not familiar with Disjoint-set data structure.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
I'm trying to find the no. of groups of friends from the given sets of friends a...
Criminate asked 17/6, 2015 at 21:56
5
Solved
I know the STL has set_difference, but I need to just know if 2 sets are disjoint. I've profiled my code and this is slowing my app down quite a bit. Is there an easy way to see if 2 sets are disjo...
Motorbus asked 26/12, 2009 at 19:31
2
Solved
Recently, I read this and was surprised that the time complexity of the union & find algorithm just with the path compression was O((m+n) log n), where m is the number of 'find' queries and n i...
Tetrabasic asked 19/7, 2014 at 10:30
4
Solved
Practicing for software developer interviews and got stuck on an algorithm question.
Given two sets of unsorted integers with array of length m and other of
length n and where m < n find an ef...
Uncircumcision asked 8/7, 2014 at 19:41
2
Solved
I have three grammars:
A -> aB | b | CBB
B -> aB | ba | aBb
C -> aaA | b | caB
I need to "determine whether [they] are LL grammars by performing the pairwise disjoint test, showing the first s...
Ankylosaur asked 29/1, 2012 at 20:17
1
I'm trying to do this exercise in Introduction to Algorithms by Cormen et al that has to do with the Disjoin Set data structure:
Suppose that we wish to add the operation PRINT-SET(x), which is ...
Stylite asked 8/4, 2014 at 18:14
2
Solved
Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint .
The optimization version of the problem, maximum ...
Pittman asked 8/3, 2014 at 17:14
4
Solved
I am having some hard time using Disjoint Sets in Connected Component Labeling. I have looked on many examples and also on this question where Bo Tian provided a very good implementation of Disjoin...
Acro asked 16/1, 2012 at 3:15
5
Solved
I'm trying to write a program that would find the minimum spanning tree. But one problem I am having with this algorithm, is testing for a circuit. What would be the best way to do this in java.
O...
Arbitration asked 27/2, 2012 at 4:7
3
Solved
Can anyone point me to some info on Disjoint sets as linked list? I cant find any code on this.
Language C++
Edroi asked 7/8, 2009 at 7:4
1 Next >
© 2022 - 2025 — McMap. All rights reserved.