Union Disjoint -Rank and Path Compression

Abhinay Gupta

·

Follow

Jul 8, 2021

--

Listen

Share

class DSU{
    //path compression and union by rank
    int[] parent;
    int[] rank;
    int components;
    public DSU(int components){
        this.components=components;
        parent = new int[components];
        for(int i =0 ; i<components;i++){
            parent[i]=i;//initially node is the parent of itself
        }
        rank = new int[components]; //initial rank=0
        
    }
    
    public int find(int node){
        if(parent[node]!=node) {
            parent[node]=find(parent[node]);
        }
        return parent[node];
    }
    
    public boolean union(int x, int y){
        int px = find(x);
        int py = find(y);
        if(px==py) return false;
        else{
        else if (rank[px]<rank[py]) parent[px]=py;
        else if(rank[px]>rank[py]) parent[py]=px;
        else { 
            parent[py]=px;
            rank[px]++;
        }
        componenets--;
        }
        return true;
    }
}