DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Disjoint set graph with union by rank and union by size

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]++;
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)