Disjoint set graph is used when we are dynamically connecting edges of the graph one by one( like we do in Krushkal's spanning tree)
When we connected two components of the graph using disjoint set we performed a union of the two parent nodes of the two components.
This union of two-parent nodes can be performed based on rank or the basis of size.
Where rank tells us which tree(component of the graph)is bigger among two trees (components of the graph) that we are trying to connect.
The size tells us how many nodes are in the union of two components we are trying to connect.
The time complexity of the disjoint set graph is already discussed here
class Disjoint{
int parent[];
int rank[];
int size[];
public Disjoint(int p[] , int r[], int s[]){
this.parent = p;
this.rank = r;
this.size = s;
}
public void makeSet(){
for(int i =0;i<parent.length;i++){
parent[i] = i;
rank[i] = 0;
size[i] = 1;
}
}
public int findParent(int node){
if(parent[node] == node) return node;
else return parent[node] = findParent(parent[node]);
}
public void unionBySize(int u, int v){
u = findParent(u);
v = findParent(v);
if(size[u] > size[v]){
parent[v] = u;
size[u] = size[u] + size[v];
}
else if(rank[v] > rank[u]){
parent[u] = v;
size[v] = size[v] + size[u];
}
else {
parent[v] = u;
size[u] = size[u] + size[v];
}
}
public void unionByRank(int u, int v){
u = findParent(u);
v = findParent(v);
if(rank[u] > rank[v]){
parent[v] = u;
}
else if(rank[v] > rank[u]){
parent[u] = v;
}
else {
parent[v] = u;
rank[u]++;
}
}
}
Top comments (0)