AntInLoop

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]++;
    }
};