Questions tagged [disjoint-sets]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
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 ...
cgss's user avatar
  • 111
2 votes
0 answers
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 ...
Hugh Mann's user avatar
0 votes
0 answers
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 ...
user159841's user avatar
0 votes
1 answer
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 ...
Ayyappa Gollu's user avatar
1 vote
1 answer
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 ...
Vallerious's user avatar
0 votes
1 answer
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 ...
SVMteamsTool's user avatar
2 votes
1 answer
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$ ...
SVMteamsTool's user avatar
2 votes
1 answer
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 "+", "-&...
stackoverload's user avatar
0 votes
2 answers
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 ...
software evolved's user avatar
1 vote
0 answers
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$...
user avatar
1 vote
1 answer
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. ...
Benny 's user avatar
  • 71
0 votes
0 answers
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 ...
pensee's user avatar
  • 131
1 vote
2 answers
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 ...
xdavidliu's user avatar
  • 858
1 vote
1 answer
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 ...
exteral's user avatar
  • 135
3 votes
0 answers
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 ...
user23013's user avatar
  • 478
1 vote
1 answer
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 ...
Abhishek Ghosh's user avatar
8 votes
1 answer
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,...
timg's user avatar
  • 234
1 vote
1 answer
211 views

Amortized analysis for disjoint sets' find-set(x) function (from CLRS)

I start off by apologizing for the fact that I don't really know how to use latex/markdown. My question, however, is directly from the Introduction To Algorithms book by Cormen et al. The topic ...
Silver Flash's user avatar
4 votes
2 answers
352 views

Testing the property of being a union of three disjoint cliques

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 ...
Ploni Almoni's user avatar