Disjoint Set Data Structure Implementation in C++

A Disjoint Set, also known as Union-Find, is a data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets. It supports two main operations:

• Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
• Union: Join two subsets into a single subset.

The Disjoint Set data structure is useful in various applications, such as network connectivity, image processing, and Kruskal’s algorithm for finding the Minimum Spanning Tree of a graph.

Program Structure

The C++ implementation of the Disjoint Set data structure will include:

1. Initialization: Creating and initializing the disjoint sets.
2. Find Operation: Implementing the find() function to determine the root of the set containing a particular element, using path compression to optimize the process.
3. Union Operation: Implementing the union() function to merge two subsets, using union by rank to optimize the merging process.

Code Implementation

#include <iostream>
#include <vector>

class DisjointSet {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    // Constructor to initialize the Disjoint Set
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) { parent[i] = i; // Each element is its own parent initially } } // Find function with path compression int find(int u) { if (parent[u] != u) { parent[u] = find(parent[u]); // Path compression } return parent[u]; } // Union function with union by rank void unionSets(int u, int v) { int rootU = find(u); int rootV = find(v); if (rootU != rootV) { if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};

// Main function to demonstrate the Disjoint Set operations
int main() {
    int n = 5; // Number of elements in the set
    DisjointSet ds(n);

    // Perform some union operations
    ds.unionSets(0, 2);
    ds.unionSets(4, 2);
    ds.unionSets(3, 1);

    // Check if elements are in the same set
    if (ds.find(4) == ds.find(0)) {
        std::cout << "4 and 0 are in the same set." << std::endl;
    } else {
        std::cout << "4 and 0 are in different sets." << std::endl;
    }

    if (ds.find(1) == ds.find(0)) {
        std::cout << "1 and 0 are in the same set." << std::endl;
    } else {
        std::cout << "1 and 0 are in different sets." << std::endl;
    }

    return 0;
}

Explanation

Initialization

The constructor initializes the parent and rank vectors. The parent vector keeps track of the parent of each element, and the rank vector is used to keep the tree flat by attaching the smaller tree under the root of the deeper tree.

Find Operation

The find() function determines the root of the set containing the element u. If u is not its own parent, the function recursively finds the root and performs path compression by making u directly point to the root. This optimization helps flatten the structure, leading to faster future queries.

Union Operation

The unionSets() function merges the sets containing elements u and v. The roots of both elements are found first. If the roots are different, the function uses union by rank to attach the tree with the lower rank under the tree with the higher rank, ensuring the tree remains as flat as possible.

Conclusion

The Disjoint Set data structure is efficient for managing and merging dynamic sets. The use of path compression and union by rank optimizes the operations, making them nearly constant time for practical purposes. This C++ implementation provides a basic but effective way to utilize Disjoint Sets in various algorithms and applications.