Disjoint Set (Weighted & Rollback DSU) Code Implementations
Production-ready Disjoint Set (Weighted & Rollback DSU) data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.
Study Disjoint Set (Weighted & Rollback DSU) Guide ยท Launch Visualizer
CPP Implementation
#include <vector>
// Disjoint Set class
class DisjointSet {
private:
std::vector<int> parent, rank;
public:
// Constructor to create and initialize an empty set
DisjointSet(int n) {
rank.resize(n, 0);
parent.resize(n);
for (int i = 0; i < n; i++)
parent[i] = i;
}
// Function to find the parent of a node
int find(int node) {
if (node == parent[node])
return node;
return parent[node] = find(parent[node]);
}
// Function to merge two subsets
void merge(int x, int y) {
x = find(x);
y = find(y);
if (rank[x] > rank[y])
parent[y] = x;
else
parent[x] = y;
if (rank[x] == rank[y])
rank[y]++;
}
};