C++ Programming Basics Lecture 8: Disjoint Set

IntroductionHello everyone, today I want to bring you a different topic:Disjoint Set👇 01Concept of Disjoint SetA disjoint set is a data structure that can dynamically maintainseveral non-overlapping sets, supporting merging and querying.The operations of a disjoint set generally consist ofthree steps:

1 Initialize each point's set to itself. Generally, this step only needs to be executed once each time this data structure is used. Regardless of the implementation method, the time complexity is linear.

2 Find the set of the element, i.e., the root node.

3 Merge the sets of two elements into one set. Generally, before merging, it should be checked whether the two elements belong to the same set, which can be implemented using the above find operation.

02Usage of Disjoint SetThere are three forms of disjoint sets.The first form, basic form:This is the most basic version, which has two implementation methods:

1 Maintain f, where f[x] stores the representative of the set containing x. Merging must be done one by one, which is very slow, but querying is efficient.

2 Use a tree structure to store each set, where each node is an element and the tree root is the representative. fa[x] represents the parent of x, fa[0]=0; merge fa[root1]=root2; this is efficient for merging but slow for querying.

The second form, advanced form:This is the advanced version, suitable for most problems, and alsohas two implementation methods:

1 Path compression continues the idea from the basic version in ②. Because querying is slow, during the query, each visited node is directly pointed to the root, achieving amortized logarithmic time complexity.

2 Union by rank records the rank at the tree root. When merging, the root with the smaller rank is made a child of the larger tree root. The rank can be defined by depth or set size, and the time complexity remains amortized logarithmic.

The third form, ultimate form:This is the ultimate version, suitable for numerous problems:

Combine path compression and union by rank. After optimizing the disjoint set with path compression and union by rank, the time complexity of a single operation approaches O(α(n)), where α(n) is the inverse Ackermann function, which grows extremely slowly and can be considered constant time in practical applications, making it very efficient.

Here is the specific implementation👇：

ll get(ll x){//Query  if(x==fa[x])return x;  return fa[x]=get(fa[x]);}void merge(ll x,ll y){//Merge  fa[get(x)]=get(y);}bool isCon(ll x,ll y){//Check connectivity  return get(x)==get(y);}

“Weighted Edges”, as the name suggests, is a disjoint set where each edge connecting two nodes has an associated weight. So how do we use this?“Weighted Edges” and “Extended Domains” disjoint sets.

We use d[x] to store the edge weight between x and fa[x], and through path compression, we can directly calculate the sum of edge weights on the path from x to get(x).

“Extended Domains”, as the name suggests, involves multiple domains to maintain the disjoint set. This algorithm is suitable for problems with multiple transitive relationships that can derive from each other.

03Practical Exercises1 Template Disjoint SetThis problem is a template problem, just having hands is enough:

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll n,m,fa[4000010],ans;ll find(ll x){if(x==fa[x])return x;return fa[x]=find(fa[x]);}int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m;for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){ ll op,x,y; cin>>op>>x>>y;if(op==2){ x=find(x),y=find(y);if(x==y)cout<<'Y';else cout<<'N'; cout<<endl; }else{ x=find(x),y=find(y); fa[x]=y; } }return 0;}

2 Legend of the Galactic HeroesThis problem is a simple weighted disjoint set, the code is as follows👇：

#include<bits/stdc++.h>using namespace std;int fa[30010],d[30010],num[30010],x,y,i,j,n,T,ans; char op;int find(int n){ if(fa[n]==n)return fa[n]; int fn=find(fa[n]); d[n]+=d[fa[n]]; return fa[n]=fn;}int main(){// freopen("galaxy.in","r",stdin); // freopen("galaxy.out","w",stdout); cin>>T; for(i=1;i<=30000;++i){ fa[i]=i; d[i]=0; num[i]=1; } while(T--){ cin>>op>>x>>y; int xx=find(x); int yy=find(y); if(op=='M'){ d[xx]+=num[yy]; fa[xx]=yy; num[yy]+=num[xx]; num[xx]=0; } if(op=='C'){ if(xx!=yy)cout<<"-1"<<endl; else cout<<abs(d[x]-d[y])-1<<endl; } } return 0;}

3 Food ChainThe idea of this problem is similar to the previous one, the key lies in designing the expression and calculation method of edge weights, the code is as follows👇：

#include &lt;iostream&gt; using namespace std;int f[100000],re[100000];int n,m,a,b,p,ans=0;int find(int a){ int fa=f[a]; if (a!=fa) { f[a]=find(fa); re[a]=(re[a]+re[fa])%3; return f[a]; } else return fa;}int main(){// freopen("eat.in","r",stdin);// freopen("eat.out","w",stdout); cin>>n>>m; for (int i=1;i<=n;i++)f[i]=i,re[i]=0; for (int i=1;i<=m;i++){ cin>>p>>a>>b; if ((a>n||b>n)||(p==2&amp;&amp;a==b)) { ans++; continue; } if (p==1){ int f1=find(a),f2=find(b); if (f1==f2&amp;&amp;re[a]!=re[b]) { ans++; continue; } else if(f1!=f2){ f[f1]=f2; re[f1]=(3-re[a]+re[b])%3; } } if (p==2){ int f1=find(a),f2=find(b); if (f1==f2){ int rela=(re[a]-re[b]+3)%3; if (rela!=1) { ans++;continue; } } else { int f1=find(a),f2=find(b); f[f1]=f2; re[f1]=(3-re[a]+re[b]+1)%3; } } } cout<<ans<<endl; return 0;}

See you next time,ヾ(￣▽￣)Bye~Bye~Previous quality content from the public account:C++ Programming Basics Lecture 1: Greedy AlgorithmScratch Programming Basics Lecture 1: Gravity and ReboundAn Interesting ExperimentC++ Programming Basics Lecture 6: Structures

Please open in the WeChat client