Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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
4
votes
0answers
26 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
40 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
18 views

What is the conversion engine problem related to?

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
31 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 ...
0
votes
0answers
21 views

UnionFind different version performance

I am studying the Union Find data structure using this material written by Sedgwick et al. I am specifically interested in the versions they call QuickFindUF, <...
3
votes
0answers
76 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
70 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
29 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
48 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
306 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
66 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 ...
1
vote
1answer
4k 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 ...
2
votes
1answer
584 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
122 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
141 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
72 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
34 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
40 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
73 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
57 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
151 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
205 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
251 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
151 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
252 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
215 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
414 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
342 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
772 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 ...
9
votes
2answers
4k 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
760 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
377 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 ...
11
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: ...