**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.me/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>↵
↵
↵
↵
~~~~~↵
↵
#### 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.me/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.me/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.me/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.me/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.me/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.me/problemset?order=BY_RATING_ASC&tags=dsu)↵
↵
↵
↵
**ALL THE BEST FOR YOUR CODING JOURNEY :)**
↵
you read the Nice blog by [user:kartik8800,2024-04-04] [ DSU Blog ](https://codeforces.me/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>↵
↵
↵
↵
~~~~~↵
↵
#### 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.me/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.me/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.me/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.me/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.me/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.me/problemset?order=BY_RATING_ASC&tags=dsu)↵
↵
↵
↵
**ALL THE BEST FOR YOUR CODING JOURNEY :)**
