Disjoint set class template

 

class DisjointSet {     vector<int>rank , par , size;     public:     DisjointSet(int n )     {         rank.resize(n+1 , 0);         parent.resize(n+1 , 0);         size.resize(n+1 , 0);             }     for(int i =1 ;i < n+1 ; i++)     {         parent[i] = i;         size[i] =1;     }         int find_u_parent(int u )     {         if(par[u] == u)         {             return u;         }         return par[u] = find_u_parent(par[u] );             }         void unionByRank(int u , int v)     {         int ulp_u = find_u_parent(u );         int ulp_v = find_u_parent(v);         if(ulp_u == ulp_v)         {             return ;         }         if(rank[ulp_u] < rank[ulp_v])         {             par[ulp_u] = ulp_v;             // rank[ulp_v] += 1;                     }         else         if(rank[ulp_u] > rank[ulp_v])         {             par[ulp_v] = ulp_u;             // rank[ulp_u] += 1;         }         else         {             par[ulp_u] = ulp_v;             rank[ulp_v] += 1;         }     }         void unionBySize(int u , int v)     {         int ulp_u = find_u_parent(u);         int ulp_v = find_u_parent(v);         if(ulp_u == ulp_v)         {             return ;         }                 if(size[ulp_u] < size[ulp_v])         {             par[ulp_u] = ulp_v;             size[ulp_v] += size[ulp_u];                     }         else         {             par[ulp_v] = ulp_u;             size[ulp_u] += size[ulp_v];                     }         }     };