Disjoint Set Data Structure – Union Find Algorithm

What is Disjoint-set data structure?

  • Represents a mathematics concept Set.
  • A disjoint-set data structure, also called a union–find data structure or merge–find set.
  • A disjoint-set data structure that keeps track of a set of elements partitioned into a number of disjoint or non-overlapping subsets.
  • It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set.
  • Plays a key role in Kruskal’s algorithm for finding the minimum spanning tree of a graph.
  • This can also be used to detect cycle in the graph.

How Disjoint Set is constructed:

  • A disjoint-set forest consists of a number of elements each of which stores an id, a parent pointer
  • The parent pointers of elements are arranged to form one or more trees, each representing a set.
  • If an element’s parent pointer points to no other element, then the element is the root of a tree and is the representative member of its set.
  • A set may consist of only a single element. However, if the element has a parent, the element is part of whatever set is identified by following the chain of parents upwards until a representative element (one without a parent) is reached at the root of the tree.

Disjoint Set Operations:

MakeSet(X): This operation makes a new set by creating a new element with a parent pointer to itself. The parent pointer to itself indicates that the element is the representative member of its own set. The MakeSet operation has O(1) time complexity.

Find(X): follows the chain of parent pointers from x upwards through the tree until an element is reached whose parent is itself. This element is the root of the tree and is the representative member of the set to which x belongs, and may be x itself.

Union(x,y): Uses Find to determine the roots of the trees x and y belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. If this is done naively, such as by always making x a child of y, the height of the trees can grow as O(n).

See the animation below for more understanding.

previous arrow
next arrow


import java.util.*;
public class DisjointSet {
static class Edge{
int source;
int destination;
public Edge(int source, int destination) {
this.source = source;
this.destination = destination;
static class Graph{
int vertices;
LinkedList<Edge>[] adjList;
ArrayList<Edge> allEdges = new ArrayList<>();
Graph(int vertices){
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i <vertices ; i++) {
adjList[i] = new LinkedList<>();
public void addEgde(int source, int destination){
Edge edge = new Edge(source, destination);
allEdges.add(edge); //add to total edges
public void makeSet(int [] parent){
//Make set- creating a new element with a parent pointer to itself.
for (int i = 0; i <vertices ; i++) {
parent[i] = i;
public int find(int [] parent, int vertex){
//chain of parent pointers from x upwards through the tree
// until an element is reached whose parent is itself
return find(parent, parent[vertex]);;
return vertex;
public void union(int [] parent, int x, int y){
int x_set_parent = find(parent, x);
int y_set_parent = find(parent, y);
//make x as parent of y
parent[y_set_parent] = x_set_parent;
public void disjointSets(){
//create a parent []
int [] parent = new int[vertices];
//iterate through all the edges and keep making the sets
for (int i = 0; i <allEdges.size() ; i++) {
Edge edge = allEdges.get(i);
int x_set = find(parent, edge.source);
int y_set = find(parent, edge.destination);
//check if source vertex and destination vertex belongs to the same set
// if in same set then cycle has been detected else combine them into one set
if(x_set==y_set) {
//do nothing
union(parent, x_set, y_set);
public void printSets(int [] parent){
//Find different Sets
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i <parent.length ; i++) {
ArrayList<Integer> list = map.get(parent[i]);
list.add(i);//add vertex
ArrayList<Integer> list = new ArrayList<>();
//Print the Different sets
Set<Integer> set = map.keySet();
Iterator<Integer> iterator = set.iterator();
int key = iterator.next();
System.out.println("Set Id: " + key + " elements: " + map.get(key));
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
graph.addEgde(0, 1);
graph.addEgde(0, 2);
graph.addEgde(1, 3);
graph.addEgde(4, 5);


Set Id: 0 elements: [0, 1, 2, 3]
Set Id: 4 elements: [4, 5]

We can optimize this algorithm by doing “Union by rank and path compression”. Click here to read about it.

Applications using Disjoint sets:

  1. Represents network connectivity.
  2. Image Processing.
  3. In game algorithms.
  4. Kruskal’s minimum spanning tree.
  5. Find cycle in undirected graphs.

Ref: wiki

5 thoughts on “Disjoint Set Data Structure – Union Find Algorithm”

    • Try in incognito, if it works in incognito then try clearing ur cache and reload the page. let us know if it is still not working

    • Union – Find is a concept which us widely used in many problem solving like detect cycle in graph, krushkal algorithm etc. I will be posting articles (in next few days )which uses this concept. Thanks for following

  1. “always making x a child of y” in Union operation should be
    “always making y a child of x”. This what is done in code.


Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.