# Questions tagged [disjoint-sets]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
31 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 ...
12 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$...
45 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 ...
71 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. ...
103 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 ...
20 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 ...
38 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 ...