# 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
52 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 ...
24 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,...
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

### On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne

I am currently studying Algorithms, Fourth Edition by Sedgewick et al. On page 226, there is an analysis of the quick-union algorithm's find() method's worst case. This is the algorithm: ...
36 views

...
24 views

### Incremental dynamic on-disk disjoint sets (incremental on-disk dynamic forest)

Problem statement I am looking for an algorithm to maintain a very large number of disjoint sets under node and edge additions. Due to the data size, keeping everything in memory is not feasible, so ...
47 views

### Why not implement Union-Find structure using root as the direct parent?

I just learned about using UF with union by rank and path compression. A path can be compressed via attaching a node to its root after Find is called on the node. If the goal here is to flatten the ...
27 views

### Data structure for identifying elements while keeping track of relation

I'm looking for a data structure representing a finite set $I$ and a $d$-relation $R \subseteq I^d$ such that the following operations can be implemented efficiently: Add a new element $i$ to $I$. ...
200 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. ...
35 views

### What algorithm can solve the conversion engine problem?

I was once asked a question, given a series of units and their ratios, such as inch, cm, gram vs pound, and a lot of potentially cryptic units and ratios, such as A, B, C, D, ... if I am given ...
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 ...
104 views

### Interesting applications of union-find

I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know: Kruskal's algorithm for MST Tarjan's off-line ...
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. ...
40 views

### Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem

I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the ...
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 ...
523 views

### How to analyze the worst case of weighted quick-union method on union-find

Here is exercise 1.5.15 in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne. Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial ...
89 views

### communities problem with union and find

I am trying to solve the following problem: Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry ...
8k views

### Why time complexity of union-find is $O(lgN)$ with only “Union by Rank”?

I'm studying time complexity of Union-Find data structure. I saw time complexity of union and find function depends on some conditions. without anything: $O(N)$ with Union by Rank: $O(\log N)$ with ...
1k views

### How to understand the complexity of Kruskal implemented with Quick-Union by rank and path compression?

I'm trying to understand the complexity of the Kruskal algorithm implemented with the Quick-Union by rank and with the path compression. Now there is a theorem for the last structure above: The ...
137 views

834 views

### Split-Find: maintaining dynamic graph connectivity information, under edge deletion

Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph? Let $G$ be an undirected graph. I have two ...
Studying Quick-Find and Quick-Union heuristic I've found clear that: with quick find trees and a union based on the size of the trees we can make a union in $T_{am}(n)=O(\log(n))$ with quick find ...
Consider a directed graph $G$ on which one can dynamically add edges and make some specific queries. Example: disjoint-set forest Consider the following set of queries: ...