Questions tagged [union-find]
Questions about the abstract data structure Union-Find (also called disjoint-set) and its realizations.
53 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
2
votes
0
answers
64
views
Is the Union-Find algorithm really based on trees?
In the Union-Find data structure (also known as the Disjoint-Set data structure), elements of a set have directed edges providing paths to the representative element, or root, of the set. Each set ...
4
votes
1
answer
123
views
Question about tidy trees (Union-Find)
The following excerpt is taken from this paper, in page 3.
Our new union-find-delete data structure, like most other
union-find data structures, maintains the elements of each set in a rooted tree.
...
1
vote
1
answer
176
views
How to create a tree of height $lg(n)$ using Union-Find data structure
I'm wondering given a set $A$ of $n$ numbers, is there any procedure that can create a tree of height $lg(n)$ that contain all the elements of $A$ by applying consecutive Union by rank operation in a ...
0
votes
0
answers
86
views
Can a binary tree be generated from Union-Find using union-by-rank?
I'm trying to determine if the following claims are true or false:
Claim 1
When disjoint Union-Find is implemented using up-trees and union-by-rank, and initially
there was a set of 5 single nodes. ...
0
votes
1
answer
67
views
How to do different cases of Union Find?
Here is the question:
I understand that the absolute parents are 1, 3, 0, and 8, respectively, but I'm not sure how to do union here. Could someone help me understand how to do this?
0
votes
0
answers
54
views
Create a class or structure like union of ranges
How to create a structure which acts as union of ranges. In that structure new ranges can be inserted beforehand and then some queries are asked to find out if the given point is covered by any of the ...
2
votes
0
answers
155
views
Difficulty in last sentence in proof of "Amortized cost of $\text{Find-Set}$ operation is $O(\alpha(n))$" from CLRS
I was reading the section of Data Structures for Disjoint Sets from the text Introduction to Algorithms by Cormen et. al. I made it through the proof, but I'm not sure I understand the very last ...
0
votes
1
answer
277
views
Does it make sense to apply path compression to kruskal algorithm?
I am reading about Kruskal and analysing it’s time complexity.
Let’s say there are E edges and V vertices.
Kruskal algorithm has two important time complexity equations ,
Sort edges- Elog(E)
For ...
3
votes
1
answer
224
views
Efficient intersection of equivalence classes
Having two equivalence relations, both as a union find data structure with the same number of elements, what is the most efficient way to find the equivalence relation that is the intersection of both ...
0
votes
1
answer
744
views
Connectivity in Directed Graph
Connectivity in undirected graph can be easily identified using Disjoint Union Set (Union Find). Is there any way to check connectivity in a directed graph efficiently other than doing Depth First ...
0
votes
1
answer
642
views
Can someone explain intuitively why union find works to find a cycle in an undirected graph?
I understand how the UF algorithm works to detect a cycle in an undirected graph, but I don't understand why it always works. Could someone explain that intuitively?
Specifically, I don't understand ...
0
votes
1
answer
148
views
Modified Union Find Data Structure
The task is to make data structure with the following operations:
query: takes two arguments s and t and returns true if they are in the same set and false otherwise.
union: takes two arguments s and ...
user avatar
user138448
1
vote
1
answer
122
views
Why merge into the larger tree in union by rank
When we do union by rank we merge the smaller tree into the larger tree. I dont understand why we do this exactly?
1
vote
1
answer
242
views
What does it mean that a set of intervals is sorted by the right and left endpoints?
While reading a paper (On the k-coloring of intervals), I came upon the following description:
"Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are ...
1
vote
2
answers
281
views
walk / traverse a disjoint set that has union rank and path compression
I'm studying CLRS section 21.3, which introduces a union rank + path-compressed implementation of disjoint set. The implementations of MAKE-SET, UNION, LINK, and FIND-SET on p 571 of the book all work ...