Understanding Disjoint Set And Their Use Cases in Computer Science

Prerequisite

1)Basic Programming skills and understanding of java
  because demo codes are in java.

2)Basic understanding of rooted trees.

      Fig 1.1: Disjoint set data strucuture with rooted tree representation along with path compression and union by rank heuristics.

Dis-joint set data structure also known as the union or find data structure is used to partition set of elements into dis-joint sets according to some criteria. Disjoint-set data structure provides nearly about constant time operations for adding a new set, merging existing set to form a  new disjoint set and to find whether two elements are in the same set.

How Are Disjoint-set data structure implemented?

Every set in a disjoint set have a representative of the set and elements within that set points to that.

Although there are certain implementations available for implementing core operations(union aka merge-set and find).Some of them are based on the linked list and some are based on rooted trees, but most efficient implementation till now is based on rooted tree combined with two heuristics which are explained below

1)Union by rank 

Union by the rank states that when two sets are merged then the representative of the set with the lower rank will point to the representative of the set with higher rank.

Note: rank is an approximation of total number element inside a set or it could be log(n) and it should be upper bound to the height of the rooted tree.

 2)Path compression

The idea of find set is used in find set operation in which all the nodes in a set will point directly to the representative of the set i.e root of the rooted tree(This will not change any rank).

For more understanding of disjoint set data structure please visit the following link: https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/

Use Cases of Dis-joint set Data Structure

1)It is used to keep track of connected component in an undirected graph.

2)It is used to detect cycles in the graph.

3)It is used to calculate the minimum spanning tree in Kruskal's algorithm.

4)It is used in Maze generation problems.

5)Calculating mutual friends.

You can use the Disjoint-set data structure wherever you need to maintain you need to maintain whose intersection is empty and you need to find which element is present in which set and merging the set.

Now let us see some sample java code which implements the Disjoint-set data structure. This code is based on the problem which is specified in the following link

https://www.hackerearth.com/practice/data-structures/disjoint-data-strutures/basics-of-disjoint-data-structures/practice-problems/algorithm/count-friends/

Now read the problem and analyze the following java code, it is based on rooted tree implementation with two heuristics stated above, before understanding following code, it is advisable to visit the top coder link to have the visual idea of  disjoint set data structure. 

import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
     
    public class DisjointSet {
     
    	Map<Integer,Node> elements=new HashMap<Integer,Node>();
     
    	class Node{
     
    		Long rank;
     
    		Integer data;
     
    		Node parent;
    		
    		Long size;
     
    		public Node(Integer data){
    			rank=0L;
    			this.data=data;
    			this.parent=this;
    			this.size=1L;
    		}
     
    		public Long getSize() {
    			return size;
    		}
     
    		public void setSize(Long size) {
    			this.size = size;
    		}
     
    		public Long getRank() {
    			return rank;
    		}
     
    		public void setRank(Long rank) {
    			this.rank = rank;
    		}
     
    		public Integer getData() {
    			return data;
    		}
     
    		public void setData(Integer data) {
    			this.data = data;
    		}
     
    		public Node getParent() {
    			return parent;
    		}
     
    		public void setParent(Node parent) {
    			this.parent = parent;
    		}
     
    	}
    	public Node find(Node n){
    		Node current=n;
    		for(current=n.getParent();current!=current.getParent();current=current.getParent()){}
    		if(n.getParent()!=current)
    			  n.setParent(current);
    		return current;
    	}
     
    	public void mergeSet(Node u,Node v){
    		Node representativeU=find(u);
    		Node representativeV=find(v);
    		if(representativeU!=representativeV){
    			int compare=representativeU.getRank().compareTo(representativeV.getRank());
     
    			switch(compare){
     
    			case 1:   
    				      representativeV.setParent(representativeU);
    					  representativeU.setSize(representativeU.getSize()+representativeV.getSize());
    			break;
     
    			case -1:  
    				      representativeU.setParent(representativeV);  
    				      representativeV.setSize(representativeV.getSize()+representativeU.getSize());
    				      break;
    			default:
    					  representativeV.setParent(representativeU);
    					  representativeU.setSize(representativeU.getSize()+representativeV.getSize());
    				      representativeU.setRank(representativeU.getRank()+1);
    				break;
    			}
    		}
    	}
    	
    	public static void main(String args[]){
    	      DisjointSet set=new DisjointSet();
    		  Scanner sc=new Scanner(System.in);
    	      String input[]=sc.nextLine().split(" ");
    	      Integer noOfStudents=Integer.parseInt(input[0]);
    	      Integer noOfRelation=Integer.parseInt(input[1]);
    	      
    	      for(int i=1;i<=noOfStudents.intValue();i++){
    	    	  set.elements.put(i, set.new Node(i));
    	      }
    	      
    	      for(int i=0;i<noOfRelation.intValue();i++){
    	    	  String relation[]=sc.nextLine().split(" ");
    	    	  DisjointSet.Node u=set.elements.get(Integer.parseInt(relation[0]));
    	      	  DisjointSet.Node v=set.elements.get(Integer.parseInt(relation[1]));
    	      	  set.mergeSet(u, v);
    	      }
    	      StringBuffer buffer=new StringBuffer("");
    	      for(int i=1;i<=noOfStudents.intValue();i++){
    	    	  DisjointSet.Node u= set.elements.put(i, set.new Node(i));
    	    	  buffer.append(set.find(u).getSize()-1+" ");
    	      }
    	      System.out.println(buffer.toString());
     
    	}
     
    }

Language: Java

Hope above code is helpful for someone.