# Questions tagged [union-find]

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

38 questions
Filter by
Sorted by
Tagged with
22 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 ...
35 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

...
23 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 ...
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$, $1$ and $2$ are friends (assuming symmetry ...
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 ...
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 ...
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 ...
191 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. ...
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$. ...
81 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 ...
6k views

228 views

### Time Complexity of a Union Find algorithm

I'm trying to understand the time complexity of an example algorithm. My conclusion was O(n^2) but this was considered wrong. The algorithm is as follows: input: data: array of sorted n integers input:...
75 views

### Union-Find with link-by-rank to represent a binary field with simple operations

I have a field $X$ of given length $n$ which is filled with zeroes in the beginning. I only need these 3 simple operations: GET_VALUE$(i)$: returns the value of $i$-th cell ($X[i]$) SET_TO_1$(i)$:...
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 ...
54 views

### an appropriate data-structure to represent a family of sets (Which supports exactly MAKE-SET(x), UNION(S1,S2), REPORT(S))

I need to represent a family F of sets with some appropriate datastructure. The datastructure needs to support the procedures MAKE-SET(x), DISJOINT-UNION(A,B) and REPORT(A). I dont have a problem with ...
76 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 ...
61 views

### Problems understanding the Union functionality of the Union-Find Algorithm

I am currently doing a course based on algorithms (Coursera). I've come across an algorithm called quick find. The course does have reference to Big O Notation. Despite the fact that I do not have ...
175 views

### How can union-find algorithm be used with “real” data

In the beginning of the Princeton algorithms course the Dynamic connectivity problem is presented (quick-find, quick-union). Here is how it's described: The input is a sequence of pairs of integers,...
242 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 ...
253 views

### Analysis of Union Find with path compresson and rank

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 ...
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 ...
343 views

### Height and depth of every node in Path Compression

If we have an union-find(disjoint-set) data structure and we are doing an union by rank and path compression for a find operation, how would the depth and height of every node change after the find ...
225 views

### Analysis of Union-Find(Disjoint Sets)

I have been trying to learn more about amortized analysis. Recently I came across the Disjoint Sets or Union-Find structures. I am using union by rank and path comparison. The potential of such data ...
505 views

### How to show that two vertices in a connected component are in the same set? (bi conditional)

Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set. The CONNECTED-COMPONENTS algorithm is the ...
398 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 ...
935 views

### Find a graph for which Kruskal's algorithm achieves worst-case running time

I am working on a problem in which I must find a graph with edge weights on n vertices, for which Kruskal's algorithm achieves worst-case running time. I am using a UNION-FIND data structure, but ...
830 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 ...
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: ...
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 ...