# Questions tagged [disjoint-sets]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
1 vote
36 views

### Set cover variation: disjoint covers for all but one element

In the classical set cover problem, we are given the set $U$ of elements $\{1, \dots, n\}$ and a collection $C$ of some subsets such that their union is the whole set. Now, I will introduce the first ...
• 111
120 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 ...
36 views

### Finding Minimum Elements for Longest Path in Disjoint Set

I want to know the minimum number of elements needed to create a tree with the longest path having n edges. How can I approach this problem using the forest implementation of disjoint sets with union ...
147 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 ...
1 vote
40 views

### Disjoint Set Constant Time Union Operation

I am following a LeetCode tutorial for Disjoint sets I have trouble understanding why the so called "Quick Find" method needs to take O(n) time. I have implemented an data structure that has ...
• 115
164 views

### Disjoint Set union complexity when makesets, unions and finds follow a certain order

Consider an arbitrary sequence of $m$ MAKESET operations, followed by $u$ UNION operations, followed by $f$ FIND operations, and let $n = m + u + f$ in a disjoint set union data structure. Prove that ...
• 433
104 views

### Bounding the height of a tree in a variant of disjoint set union

Consider a variant of link-by-size implementation of the Union–Find data structure, in which trees will be linked by the logarithm of the size. Let $\ell_i$ = $⌊\log_2|T_i|⌋$ and, when merging $T_i$ ...
• 433
90 views

### Make maze connected by removing internal walls

Recently I've stumbled upon a strange graph problem. Here is a brief description. Given $n\times m$ matrix with $2n + 1$ rows such that each row contains $2m + 1$ characters "+", "-&...
982 views

### Disjoint Set deletion

The wikipedia entry for disjoint set data structure includes the statement (in the "Applications" section) Note that the implementation as disjoint-set forests does not allow the deletion ...
1 vote
13 views

### Algorithm to check if a family contains two disjoint sets

Let $\mathcal F_1$ and $\mathcal F_2$ be a families of subsets of $\{1,\dots, m\}$. Such that $|\mathcal F_1| = n_1$ and $|\mathcal F_2| = n_2$. I would like to check if there is $f_1\in \mathcal F_1$...
1 vote
357 views

### Check if two graphs are edge-disjoint

Two undirected graphs $G$ and $H$ on the vertices $1,2,\ldots,n$ are disjoint if the intersection of their edge sets is empty. Assume both $G$ and $H$ are represented by adjacency matrices. ...
• 71
184 views

### Augment the tree data structure for disjoint sets to implement the PRINT operation

Consider the following new operation for disjoint sets PRINT(x): print every element in S_x the set containing x One Approach that I found but couldn't figure out completely : In addition to tree we ...
• 131
1 vote
194 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 ...
• 858
1 vote
45 views

### Definition of Disjointness for binary strings

Basically, most of the definition for disjointness are such that $DISJ(A, B) = 1$ if $A \cap B = \emptyset$ and $DISJ(A, B) = 0$ for other case. My confusion is how is $0$'s influence in here. For ...
• 135
62 views

### What's the best non-amortized disjoint set?

In practice, the amortized O(α(n)) data structure is good for every case. But if I want to be pedantic and require each operation to be under a certain time complexity, what's the currently known best ...
• 478
1 vote
213 views

### Difficulty in few steps in proof of "Amortized cost of $\text{Find-Set}$ operation is $\Theta(\alpha(n))$"assuming union by rank, path compression

I was reading the section of data structures for disjoint sets from the text Introduction to Algorithms by Cormen et. al .I faced difficulty in understanding few steps in the proof of the lemma as ...
• 1,122
5k views

### Runtime difference bewteen Union by Rank and Union by Size for union-find

I was studying Union Find, and according to Wikipedia, there are 2 types of union: union by rank and Union by size. My question is, what is the runtime difference between the two (if any)? Intuitively,...
• 234
1 vote
Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of three disjoint cliques. I've been sitting for a few hours and I don't have any idea of how to ...