23.DisjointSet.md

Disjoint set data structure or Union-Find

• This is used to find out, if two nodes are given then whether they belong to same component or not

• It consists of two operations, findPar() and union() operation. findPar() will help to find the parent of the node, and union() will help you to combine two components i.e union(u, v) will combine the component in which u is and the component in which v is.

• Disjoint set data structure is used in Kruskal's algorithm in detecting a cycle and at lot of places in CP.

• Now union means, that combining the two components such that they have common parents

The efficient implementation of DISJOINT SET is done by Union by rank and path compression

Basically we'll do the union of two components based on their rank

1. Inititally every node is parent of itself

right now, if i will ask the parent of 3, then it will return 3, as every node is the parent of itself

2. And we will also maintain another array called rank array which will contain rank of all the elements, initial rank of everyone will be zero.

3. First of all you are asked to do the union of 1 and 2, i.e union(1, 2), therefore we will find the parent of 1 and 2, we can see the parent of 1 is 1 and parent of 2 is 2, now find out the rank of both the parents, if both of them have same rank then either attach 1 with 2 or attach 2 with 1, doesn't matter.
4. Else if both have different ranks, then attach the one having the smaller rank with the one having the greater rank.
5. and just make sure to increase the rank by 1 of the guy to whom you are attaching to, here if we'll attach 2 with 1 then increase the rank of 1 by 1

6. Now union(2, 3), so first of all find the parent of 2 and 3, as parent of 2 is 1 and parent of 3 is 3, now rank of 2's parent i.e 1 is 1 and rank of 3's parent i.e 3 is 0, as rank of 1 > rank of 3, so 3 will be attached with 1, and whenever the ranks are different, then there is no need to increase the rank

Now why we aren't attaching the components directly but attaching them by comparing the ranks, the reason is that if we'll not compare the ranks and will attach directly then it will elongate the tree, increasing the depth of the tree results in increasing the time complexity of finding parent

something like this:

So this was the Union by rank, now let us see what is the path compression:

Now in this case:

we can see that the parent of 7 is 6, and parent of 6 is 4, basically parent of 7 is 4, but we have to traverse all the way through the treeto find the final parent, so what we can do is, we can compress the path by joining the 7 directly with 4, i.e you don't need to caluclate it again and again, once you calculate that the parent of 7 is 4, then just connect 7 with 4, so that next time you don't need to calculate the parent of 7 again.

similarly you can do this for all of them

Path compression allows to minimize the number of movements while finding the parent of a node

Time complexity and space complexity

• Time complexity of performing both union() and findPar() operation together takes O(4 * alpha) which is nearly equal to O(4), therefore performing both union and find operation m times will take O(m * 4 * alpha) which is equal to O(m * 4)

• Space complexity would be O(2n) as we are using a rank array and a parent array

Code will not run, it is just for reference

/*
step 1: makeSet - set each element to be its own parent and rank of each element to be 0
step 2: findpar - find the ultimate parent of each element
step 3: do the path compressing in findpar
step 4: union - find the union of two nodes

*/

#include<bits/stdc++.h>
using namespace std;

int rank[100000];
int par[100000];

//set each element to be its own parent and rank of each element to be 0
void makeSet(){
    for(int i=0; i<100000; i++){
        par[i] = i;
        rank[i] = 0;
    }
}

//find the ultimate parent of each element
int findpar(int node){
    if(par[node] == node){
        return node;
    }
    //path compression by storing the values
    return par[node] = findpar(par[node]);
}

//find union of two elements
void union(int u, int v){
    //first of all find the parent of both the elemnts
    u = findpar(u);
    v = findpar(v);
    
    //rule : smaller will attach with larger
    //if same rank then anybody can be attached with anyone
    
    //if the rank of the u's parent is greater then attach v with u
    if(rank[u]>rank[v]){
        //attaching v with u, i.e set the parent of v as u
        par[v] = u;
    }
    
    //if the rank of the v's parent is greater then attach u with v
    else if(rank[v]>rank[u]){
        //attaching u with v, i.e set the parent of u as v
        par[u] = v;
    }
    
    //if parent of both u and v have same rank then you can attach anyone with anyone
    else if(rank[u] == rank[v]){
        //let us say I attached u with v
        par[u] = v;
        //then increase the rank of v by 1, as v is ultimate parent now
        rank[v]++;
    }
}

int main(){
    makeSet();
    int m;
    cin>>m;
    while(m--){
        int u, v;
        cin>>u>>v;
        union(u, v);
    }
    
    //let us check if 2 and 3 belong to same component 
    if(findpar(2) != findpar(3)){
        cout<<"Different component";
    }else{
        cout<<"Same component";
    }
    return 0;
}