Questions tagged [disjoint-sets]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
92 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 ...
user avatar
2 votes
1 answer
57 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$ ...
user avatar
2 votes
1 answer
32 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 "+", "-&...
user avatar
0 votes
2 answers
217 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 ...
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
128 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. ...
user avatar
  • 51
0 votes
0 answers
107 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 ...
user avatar
  • 31
1 vote
2 answers
87 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 ...
user avatar
  • 818
1 vote
1 answer
25 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 ...
user avatar
  • 135
3 votes
0 answers
46 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 ...
user avatar
  • 478
1 vote
1 answer
128 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 ...
user avatar
4 votes
1 answer
2k 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,...
user avatar
  • 184
1 vote
1 answer
127 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 ...
user avatar