# Questions tagged [union-find]

Questions about the abstract data structure Union-Find (also called disjoint-set) and its realizations.

39 questions
Filter by
Sorted by
Tagged with
7k views

244 views

### Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?

Look at this solution: Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION ...
160 views

### Reachability queries on uncertain graphs

We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the ...
97 views

### Using Union find to check whether there is a cycle in a graph

I'm trying to learn about DSU, and I came across a point stating if two vertices belong to the same sub-set, then a cycle exists. In terms of implementation of DSU, I'm unable to make sense of this. ...
199 views

### Why does Union-Find have time complexity O(N + M lg* N) with the “log star N”?

The time complexity of Weighted Union-Find with Path Compression, for M union-find ops and N objects is said to be $$O(N + M \lg^*N)$$ and the $lg^*N$ is "log star N" and is iterated logarithm. ...
87 views

### Given N vertices and M edges find if two nodes are in the same connected component?

Given a set of $n$ people and $m$ friendship relations between those people (relation is between two persons) we need to suggest a data structure that supports the division of those people into ...
35 views

### Union-Find link-by-rank preserve a root

Suppose I have two union-find trees with roots $x$ and $y$ respectively. I want to join them in constant time (this is normally possible since I already "hold" the roots) but I need $x$ to be the root ...
78 views

### Best way to fusion two list of clusters

Imagine the following sets : A = Set( sortedSet(1,2,3), sortedSet(4,8)) B = Set( sortedSet(3,4), sortedSet(5,6,7) ) Where each inner list represent a cluster ...
399 views

### Complexity of testing membership in a disjoint set

I have a disjoint set data structure (sometimes known as a union-find data structure) where I store a value in each "node". I want to look up a node by value. How can I do this? The representations ...
7 views

### On the complexity analysis of weighted quick union in algorithms 4th edition by Sedgewick and Kevin Wayne

I've been studying Sedgewick's book and tried to count the number of array accesses for weighted quick union in the worst case. There is a diagram for this on the left side of page 229 in the fourth ...
36 views

...
104 views

### DSU algorithm optimization

We know how DSU(Disjoint Set Union) can be used to find the connectivity between two users. However, I was wondering if it can be used with a Segment Tree. Let me explain my idea further. Suppose we ...
I have been given that $n$ make-sets and $m \ge k$ finds and $k$ unions can be performed in $O(n + m \log^*(k))$ time (I'm aware of the ackermann function but am not interested in proving that). Where ...