Disjoint set

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:


import java.util.HashMap;
import java.util.Map;

public class DisjointSet {

    Map<Integer,Node> map = new HashMap<>();
    class Node{
        int rank;
        int data;
        Node parent;
    }

    Node make(int val){
        Node node = new Node();
        node.data = val;
        node.rank = 0;
        node.parent = node;
        map.put(val,node);
        return node;
    }
    boolean union(int n1, int n2){
        Node node1 = map.get(n1);
        Node node2 = map.get(n2);

        Node parent1 = findSet(node1);
        Node parent2 = findSet(node2);
        if(parent1.data==parent2.data){
            return false;
        }
        if(parent1.rank>=parent2.rank){
            parent1.rank = (parent1.rank==parent2.rank)? parent1.rank+1:parent1.rank;
            parent2.parent = parent1;
        }else {
            parent1.parent = parent2;
        }
        return true;
    }
    Node findSet(Node node){
        Node parent = node.parent;
        if(node==parent){
            return parent;
        }else{
            node.parent = findSet(node.parent);
        }
        return node.parent;
    }

    int findSet(int val){
        return findSet(map.get(val)).data;
    }

    public static void main(String[] args) {
        DisjointSet ds= new DisjointSet();
        ds.make(1);
        ds.make(2);
        ds.make(3);
        ds.make(4);
        ds.make(5);
        ds.make(6);
        ds.make(7);

        ds.union(1, 2);
        ds.union(2, 3);
        ds.union(4, 5);
        ds.union(6, 7);
        ds.union(5, 6);
        ds.union(3, 7);

        System.out.println(ds.findSet(1));
        System.out.println(ds.findSet(2));
        System.out.println(ds.findSet(3));
        System.out.println(ds.findSet(4));
        System.out.println(ds.findSet(5));
        System.out.println(ds.findSet(6));
        System.out.println(ds.findSet(7));

    }

}

Ref: https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/DisjointSet.java