Union Disjoint -Rank and Path Compression

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;
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store