Implementation of DisjointSet Data Structure
Learn about the disjointset data structure.
We'll cover the following
The disjointset data structure (also known as the unionfind data structure) is useful for implementing Kruskal’s algorithm, but it is also useful, in general, for checking equivalences. Two elements that are equivalent, under any notion of equivalence, can be thought of as belonging to the same equivalence class and equivalence classes are essentially disjoint sets.
Operations
We go over one of the ways to implement the following methods supported by the disjointset data structure.

DisjointSet(x)
: Create a set containing the elementx
. 
Find(x)
: Find the name of the set containing the elementx
. 
Union(x, y)
: Merge the sets namedx
andy
.
Implementation as rooted trees
A single set is implemented as a rooted tree, where the tree is named after the name of the element present at the root.

Each node has a
parent
pointer that points to the parent of that node in the rooted tree. 
The
parent
pointer of the root points to the root itself.
Get handson with 1200+ tech skills courses.