Skip to main content

union-find

 Union-Find (or Disjoint Set Union, DSU) is a data structure that tracks elements partitioned into disjoint subsets, supporting rapid merging () and representative finding () operations.

Optimized with path compression and union by rank/size, it achieves near-constant amortized time complexity, $O(\alpha(n))$, making it efficient for Kruskal’s algorithm and dynamic connectivity. [1, 2, 3, 4]


Key Concepts and Operations
  • Find(x): Determines the representative (root) of the set containing element .
  • Union(x, y): Merges the sets containing elements and .
  • MakeSet(x): Initializes a new set containing only element .
  • Structure: Typically implemented as a forest of trees, where each node points to its parent. The root of a tree is its own parent and acts as the representative. [4, 5, 6, 7, 8]
Optimizations
  • Path Compression: During a operation, makes every node on the path point directly to the root, flattening the tree.
  • Union by Rank/Size: Always attaches the smaller tree under the root of the larger tree to keep the tree shallow. [2, 8, 9]
Applications
  • Graph Algorithms: Finding connected components and Kruskal's algorithm for Minimum Spanning Trees (MST).
  • Cycle Detection: Efficiently checking if adding an edge creates a cycle in an undirected graph.
  • Dynamic Connectivity: Tracking network connections. [3, 10]
Complexity
  • Space: $O(n)$ to store parents and ranks.
  • Time: Almost $O(1)$ amortized per operation when using both optimizations ($O(\alpha(n))$, where $\alpha$ is the Inverse Ackermann function). [1, 2, 9, 11, 12]

code in c++ :

#include <vector>
#include <numeric>
#include <iostream>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank; // Or size, to keep track of tree height/size

public:
    // Constructor: Initializes each element as its own set with rank 0
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 0); // Initialize ranks to 0
        std::iota(parent.begin(), parent.end(), 0); // Fill parent array with 0, 1, ..., size-1
    }

    // Find operation with path compression
    int find(int i) {
        if (parent[i] == i)
            return i;
        // Path compression: set the parent of i to its ultimate root
        return parent[i] = find(parent[i]); 
    }

    // Union operation with union by rank
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);

        if (root_i != root_j) {
            // Union by rank: attach the smaller rank tree under the larger rank tree
            if (rank[root_i] < rank[root_j]) {
                parent[root_i] = root_j;
            } else if (rank[root_i] > rank[root_j]) {
                parent[root_j] = root_i;
            } else {
                // If ranks are the same, attach one to the other and increment the rank of the new root
                parent[root_j] = root_i;
                rank[root_i]++;
            }
        }
    }

    // Helper function to check if two elements are in the same set
    bool connected(int i, int j) {
        return find(i) == find(j);
    }
};

int main() {
    // Example usage
    UnionFind uf(5); // Create a UnionFind for 5 elements (0 to 4)

    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);

    std::cout << "Are 0 and 2 connected? " << (uf.connected(0, 2) ? "Yes" : "No") << std::endl; // Yes
    std::cout << "Are 0 and 4 connected? " << (uf.connected(0, 4) ? "Yes" : "No") << std::endl; // No

    uf.unite(0, 4);
    std::cout << "After union, are 0 and 4 connected? " << (uf.connected(0, 4) ? "Yes" : "No") << std::endl; // Yes

    return 0;
}


References:
Labels:

Comments

Post a Comment