Disjoint Set Data Strucuttures Problems
Difference between en1 and en2, changed 15 character(s)
**The below article is an attempt to create a good starting point for people who practice some good DSU problems**↵

you read the Nice blog by [user:kartik8800,2024-04-04] [ DSU Blog ](https://codeforces.net/blog/entry/120381) here you tell basics to advanced about DSU ↵
 ↵

below code is written by striver you can take reference from his YT channel TAKE U FORWARD ↵
 ↵


[user:striver_79,2024-04-04]↵

<spoiler summary="standard DSU ">↵
class disjointset{↵
public:↵
    vector<int> rank,parent,size;↵
 ↵
    disjointset(int n){↵
       rank.resize(n+1,0);↵
       parent.resize(n+1);↵
       size.resize(n+1);↵
 ↵
       for(int i=0;i<n;i++){↵
          parent[i] = i;↵
          size[i] = 1;↵
       }↵
    }↵
 ↵
    int findUPar(int node){↵
       if(node == parent[node]){↵
          return node;↵
       }↵
       return parent[node] = findUPar(parent[node]);↵
    }↵
    ↵
    void unionBySize(int u,int v){↵
       int ulp_u = findUPar(u);↵
       int ulp_v = findUPar(v);↵
       if(ulp_u == ulp_v) return;↵
       if(size[ulp_u] < size[ulp_v]){↵
          parent[ulp_u] = ulp_v;↵
          size[ulp_v]+=size[ulp_u];↵
       }↵
       else{↵
          parent[ulp_v] = ulp_u;↵
          size[ulp_u]+=size[ulp_v];↵
       }↵
    }  ↵
 };↵
</spoiler>↵

![ ](/predownloaded/ed/8c/ed8c298517830110084922098c8382fcb9b9dc43.png)↵

~~~~~↵

#### PROBLEM 1↵

~~~~~↵


 ↵
**1 ->** This Problem Based how we can use DSU beautifully by sorting the edges of the graph  ↵


[problem:1213G]↵

<spoiler summary="Hint 1">↵
...take the input of the edges and sort them :)↵
</spoiler>↵

<spoiler summary="Hint 2">↵
...also take the query in input and sort and accordingly join the edges↵
</spoiler>↵


<spoiler summary="DSU code">↵
struct DSU{ ↵
vll parent,size;↵
DSU(ll n){ ↵
size.assign(n,1);↵
parent.assign(n,0);↵
fl(i,n){↵
parent[i]=i;↵
}↵
}↵

ll upar(ll x){↵
if(parent[x]==x)return x;↵
return parent[x]=upar(parent[x]);↵
}↵

void merge(ll a,ll b){↵
a=upar(a),b=upar(b);↵
if(a==b)return;↵
ll psize=size[a];↵
size[a]+=size[b];↵
parent[b]=a;↵
ans+=(ncr(size[a])-ncr(size[b])-ncr(psize));↵
} ↵
};↵
</spoiler>↵

[Check my submission](https://codeforces.net/contest/1213/submission/253898407)↵


~~~~~↵

#### PROBLEM 2↵

~~~~~↵

**2 ->** This Problem is easy side of DSU to make the network connected↵

[problem:25D]↵

<spoiler summary="Hint 1">↵
are you sure you need hint ,this is standard problem↵
</spoiler>↵

 ↵

<spoiler summary="DSU code">↵
struct DSU{↵
vll parent,size;↵
DSU(ll n){↵
parent.resize(n);↵
size.resize(n);↵
fl(i,n){↵
parent[i]=i;↵
size[i]=i;↵
}↵
}↵

ll upar(ll x){↵
if(parent[x]==x)return x;↵
return parent[x]=upar(parent[x]);↵
}↵

void merge(ll a,ll b){↵
a=upar(a);↵
b=upar(b);↵
parent[b]=a;↵
size[a]+=size[b];↵
}↵
};↵
</spoiler>↵

[Check my submission](https://codeforces.net/contest/25/submission/253940304)↵


~~~~~↵

#### PROBLEM 3↵

~~~~~↵

**3 ->**  you have to make forest by adding edges by making two DSU↵


[problem:1559D1]↵

<spoiler summary="Hint 1">↵
nake two DSU for m1 and m2 and connect them and also avoid cycle similar to previous question↵
</spoiler>↵

 ↵

<spoiler summary="DSU code">↵
struct DSU{↵
vll parent,size;↵
DSU(ll n){↵
parent.resize(n);↵
size.resize(n);↵
fl(i,n){↵
parent[i]=i;↵
size[i]=i;↵
}↵
}↵

ll upar(ll x){↵
if(parent[x]==x)return x;↵
return parent[x]=upar(parent[x]);↵
}↵

void merge(ll a,ll b){↵
a=upar(a);↵
b=upar(b);↵
parent[b]=a;↵
size[a]+=size[b];↵
}↵
};↵
 ↵
</spoiler>↵

[Check my submission](https://codeforces.net/contest/1559/submission/253946386)↵

~~~~~↵

#### PROBLEM 4↵

~~~~~↵

**4 ->** This Problem Based how we can minimise the or of the no by making highest bit to Zero↵


[problem:1624G]↵

<spoiler summary="Hint 1">↵
try to make highest bit Zero↵
</spoiler>↵

 ↵

<spoiler summary="DSU code">↵
struct DSU{↵
vll par,size;↵
DSU(ll n){↵
par.resize(n);↵
size.resize(n);↵
fl(i,n){↵
par[i]=i;↵
size[i]=1;↵
}↵
}↵

ll upar(ll x){↵
if(par[x]==x)return x;↵
return par[x]=upar(par[x]);↵
}↵

void merge(ll a,ll b){↵
a=upar(a);b=upar(b);↵
if(a==b){↵
return;↵
}↵
par[b]=a;↵
size[a]+=size[b];↵
}↵

ll sz(ll x){↵
return size[upar(x)];↵
}↵
};↵
 ↵
</spoiler>↵

[Check my submission](https://codeforces.net/contest/1624/submission/254447582)↵

~~~~~↵

#### PROBLEM 5↵

~~~~~↵

**5 ->** This Problem Based how we can use DSU to connect the edges from edge weight form low to high↵


[problem:1468J]↵

<spoiler summary="Hint 1">↵
try to connect min weight node with the all node↵
</spoiler>↵

 ↵

<spoiler summary="DSU code">↵
struct DSU{↵
vll par,size;↵
DSU(ll n){↵
par.resize(n);↵
size.resize(n);↵
fl(i,n){↵
par[i]=i;↵
size[i]=1;↵
}↵
}↵

ll upar(ll x){↵
if(par[x]==x)return x;↵
return par[x]=upar(par[x]);↵
}↵

bool merge(ll a,ll b){↵
a=upar(a);b=upar(b);↵
if(a==b){↵
return 0;↵
}↵
par[b]=a;↵
size[a]+=size[b];↵
return 1;↵
}↵

ll sz(ll x){↵
return size[upar(x)];↵
}↵
};↵
</spoiler>↵

[Check my submission](https://codeforces.net/contest/1468/submission/254453566)↵


this is good level 5 problem enough to Grasp the concepts if you want to try more prblem try this [Codeforces DSU Problems](https://codeforces.net/problemset?order=BY_RATING_ASC&tags=dsu)↵



**ALL THE BEST FOR YOUR CODING JOURNEY :)**

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English utkarsh_108 2024-04-04 22:41:31 15 Tiny change: ' to high\n[problem' -> ' to high\n\n\n[problem'
en1 English utkarsh_108 2024-04-04 20:45:37 5450 Initial revision (published)