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 |
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
