Union-Find, Data Structures

Union-Find Data Structure

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;

public:
    // Constructor to initialize Union-Find with n elements
    UnionFind(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 the representative or root of the set containing 'vertex'
    int find(int vertex) {
        if (parent[vertex] != vertex) {
            parent[vertex] = find(parent[vertex]); // Path compression
        }
        return parent[vertex];
    }

    // Union the sets containing 'u' and 'v'
    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU != rootV) {
            // Union by rank
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};

Explanation of the Union-Find Class

The Union-Find data structure, also known as Disjoint Set Union (DSU), is used to manage and merge disjoint sets efficiently. It’s particularly useful in scenarios involving connected components and cycle detection in graphs.

Key Components

1. Parent Array:

   • Purpose: Keeps track of the parent or representative of each set.
   • Initialization: Each element is its own parent initially.
   • Find Operation: To find the representative of a set containing a particular element. This operation involves path compression to make future queries faster.

2. Rank Array:

   • Purpose: Used to keep track of the tree depth (or rank) for union operations. This helps to keep the tree shallow, optimizing the find operation.
   • Union Operation: To merge two sets. The root of the set with higher rank becomes the parent of the root of the set with lower rank. If ranks are equal, one root becomes the parent of the other and its rank is incremented.

Operations

1. Find:

   • Function: find(int vertex)
   • Details: Returns the representative of the set containing the vertex. Implements path compression to make future find operations faster. When a find operation is performed, it updates the parent of each node along the path to point directly to the root, thus flattening the structure.

2. Union:

   • Function: void unite(int u, int v)
   • Details: Merges the sets containing the two specified elements. Uses union by rank to keep the tree balanced. This helps to keep operations efficient, reducing the time complexity.

Use Cases

• Connected Components: Used to determine and merge connected components in a graph.
• Cycle Detection: Useful in algorithms like Kruskal’s Minimum Spanning Tree algorithm to detect cycles.

The Union-Find structure is efficient for scenarios where you need to repeatedly merge sets and query the representative of each set. It is widely used in network connectivity, image processing, and other fields where dynamic connectivity is a key concern.