Questions tagged [union-find]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
60 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 ...
2
votes
1answer
35 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,...
0
votes
0answers
8 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 ...
1
vote
1answer
39 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: ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
4
votes
0answers
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$. ...
0
votes
1answer
230 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. ...
1
vote
1answer
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 ...
0
votes
1answer
93 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 ...
3
votes
0answers
111 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 ...
0
votes
1answer
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. ...
1
vote
1answer
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 ...
0
votes
0answers
108 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 ...
1
vote
2answers
540 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 ...
1
vote
1answer
92 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 ...
3
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
0answers
138 views

Sequence of operations of Union-Find of length $m$ ($n$ being the number of Make-Set operations) with time complexity in $\Omega(m\log n)$

In Union-Find with link-by-rank but no path compression find a sequence of operations Make-Set, Find, Union of length $m$, containing $n$ Make-Set operations, and with time complexity in $\Omega(m\log ...
2
votes
1answer
242 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:...
3
votes
2answers
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)$:...
0
votes
1answer
36 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 ...
1
vote
1answer
57 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 ...
0
votes
2answers
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 ...
1
vote
1answer
62 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 ...
2
votes
2answers
177 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,...
1
vote
1answer
248 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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
354 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 ...
0
votes
0answers
227 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 ...
1
vote
1answer
512 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 ...
0
votes
1answer
404 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 ...
4
votes
1answer
943 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 ...
11
votes
2answers
7k views

Complexity of union-find with path-compression, without rank

Wikipedia says union by rank without path compression gives an amortized time complexity of $O(\log n)$, and that both union by rank and path compression gives an amortized time complexity of $O(\...
6
votes
2answers
840 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 ...
3
votes
1answer
420 views

Quick union and heuristic by size

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 ...
12
votes
1answer
4k views

Directed union-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: ...