Home »
Data Structure
Disjoint Set ADT
In this article, we are going to see what is disjoint set ADT, Application of disjoint set ADT.
Submitted by Radib Kar, on September 11, 2020
Disjoint set is an important mathematical concept which is an abstract data structure too. Disjoint sets mean a collection of elements without any specific order. To implement disjoint set ADT, an array is enough also. ADT set is an auxiliary data structure used to solve many algorithmic problems based on graphs.
Disjoint Sets ADT
The basic operations on a disjoint set are the below ones:
 MAKESET(X): create a new set with element X
 UNION(X, Y): creating a set with X & Y and it deletes individual sets of X & Y.
 FIND(X): It finds the set in which X is there. (X can't be in two different sets since it's named as disjoint set ADT)
Figure 1: Disjoint set ADT
The above is an example of disjoint set ADT whereas the below one is not since it's not disjoint.
For the below disjoint sets we show the ADT operations,

MAKESET(X), MAKESET(Y) creates two disjoint sets having element X & Y.
Like below:
 FIND(X): It returns name of the set where X exists which is here set1

UNION(X, Y): It creates a new set with element X & Y and removes the old sets of X & Y. so UNION(X, Y) returns the below:
Application of disjoint set ADT
 Representing network connectivity
 Finding cycle in an undirected graph
 Kruskal's Minimum spanning tree algorithm
 In gaming algorithms'
Here we saw the theoretical concepts behind the disjoint set ADT and in further articles we are going to application of disjoint set ADT.
Disjoint Set problems (programs on Disjoint Set)
 Find disjoint sets in a graph using disjoint set ADT operations FIND, UNION
 Finding a cycle in an undirected graph using Disjoint Sets
TOP Interview Coding Problems/Challenges