What is a Union Find Data Structure?

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.

NOTE: sets of connected objects are called connected components.

Applications of a Union Find Structure

• Dynamic Connectivity in Networks

• Percolation Problems

• Graph algorithms

• and much more!