Skip to content

Instantly share code, notes, and snippets.

@tasfik007
Created August 19, 2022 13:35
Show Gist options
  • Save tasfik007/9e4266c3fe29f841cdf721307325107d to your computer and use it in GitHub Desktop.
Save tasfik007/9e4266c3fe29f841cdf721307325107d to your computer and use it in GitHub Desktop.
Disjoint Set Union by rank and path compression
#include<bits/stdc++.h>
using namespace std;
class DSU {
vector<int> parent;
vector<int> rank;
public:
DSU (int nodes) {
vector<int> temp(nodes);
parent = temp;
rank = temp;
for(int i=0; i<nodes; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int getParent(int node) {
if(node == parent[node])
return node;
return parent[node] = getParent(parent[node]);
}
void makeUnion(int a, int b) {
int pa = getParent(a);
int pb = getParent(b);
if(rank[pa] == rank[pb]) {
parent[pb] = pa;
rank[pa]++;
} else {
if(rank[pa] < rank[pb])
parent[pa] = pb;
else parent[pb] = pa;
}
}
void printParents() {
for(int i=0; i<parent.size(); i++) {
cout<<"Node: "<<i<<" Parent: "<<parent[i]<<endl;
}
}
};
// int main() {
// DSU *dsu = new DSU(10);
// dsu->makeUnion(1,2);
// dsu->makeUnion(4,5);
// dsu->makeUnion(6,7);
// dsu->makeUnion(5,6);
// cout<<dsu->getParent(7)<<endl;
// return 0;
// }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment