Disjoint Set Data Structures
A disjoint-set data structure is defined as one that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
A union-find algorithm is an algorithm that performs two useful operations on such a data structure:
- Find: Determine which subset a particular element is in. This can determine if two elements are in the same subset.
- Union: Join two subsets into a single subset. Here first we have to check if the two subsets belong to the same set. If not, then we cannot perform union.
Applications of Disjoint set Union:
|
S. No. |
Problem |
Practice link |
|
1 |
||
|
2 |
||
|
3 |
||
|
4 |
||
|
5 |
City With the Smallest Number of Neighbors at a Threshold Distance |
Practice problems for DSU:
|
Problem |
Difficulty |
|---|---|
|
Difference between Smallest and Largest Component of the graph after each Query |
Easy |
|
Easy |
|
|
Medium |
|
|
Medium |
|
|
Medium |
|
|
Minimum difference between components of the Graph after each query |
Hard |
|
Hard |
|
|
Hard |
Contact Us