Disjoint Set | Union by Rank | Union by Size | Path Compression

1. Why Do We Need a Disjoint Set Data Structure?

In graph theory and algorithm design, we frequently encounter disjoint components within a graph. Consider a scenario where a graph has multiple disconnected components (e.g., Nodes 1, 2, 3, 4 forming one component, and Nodes 5, 6, 7 forming another).

If a user or query asks:

"Do node 1 and node 5 belong to the same connected component?"

The Brute-Force Approach

• Mechanism: Run a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from node 1 and check if node 5 is visited.
• Time Complexity: $\mathcal{O}(V + E)$ where $V$ is vertices and $E$ is edges.
• Limitation: In dynamic graphs where edges are continuously added or configuration changes happen at every instant, running linear traversals for every query is extremely inefficient and slow.

The Disjoint Set (DSU) Solution

The Disjoint Set data structure (also known as Union-Find or Merge-Find Set) solves this exact problem by answering component connectivity queries in nearly constant time ($\alpha$) and efficiently managing dynamic graphs.

2. Core Operations of Disjoint Set

A Disjoint Set data structure fundamentally supports two primary operations:

1. findParent(node): Determines the representative or ultimate parent (boss) of the component to which the node belongs. This helps check if two nodes share the same ultimate parent.
2. union(u, v): Merges two separate components containing nodes u and v into a single connected component. Union can be implemented using two principal optimizations:
   • Union by Rank
   • Union by Size

3. Real-Life Analogy: Corporate Hierarchies and Company Mergers

Real-Life Analogy

Imagine independent startup companies where every employee is initially the CEO of their own one-person company.

• When two companies decide to merge (union), instead of reorganizing the entire corporate ladder, we find the ultimate head executives (founders/ultimate parents) of both companies and subordinate the smaller company under the larger company.
• When someone asks if Employee A and Employee B work for the same overarching corporate group (findParent), we trace up the management chain to find their ultimate corporate bosses. If both trace back to the exact same top boss, they belong to the same company.

4. Naive Approach vs. Optimized DSU Architecture

Without optimizations, tree structures formed during union operations can degenerate into linear chains (resembling linked lists), causing findParent operations to degrade to $\mathcal{O}(N)$ time complexity.

The Optimization Strategy

To guarantee near-constant time performance ($\mathcal{O}(4\alpha)$), we combine two crucial algorithmic strategies:

1. Balanced Tree Attachment (Union by Rank or Union by Size) to keep tree heights shallow.
2. Path Compression during findParent traversals to flatten trees dynamically.

5. Step-by-Step Evolution: Union by Rank

Union by Rank keeps track of the "rank" (approximate depth or height) of trees to ensure that smaller trees are always attached under the roots of larger trees.

Initial Configuration Arrays

• parent Array: Stores the direct parent of each node. Initially, every node is its own parent (parent[i] = i).
• rank Array: Stores the rank of each node. Initially initialized to 0 for all nodes (rank[i] = 0).

Pseudocode: Union by Rank

function findUltimateParent(u):
    if u == parent[u]:
        return u
    return parent[u] = findUltimateParent(parent[u])  // Path compression

function unionByRank(u, v):
    rootU = findUltimateParent(u)
    rootV = findUltimateParent(v)
    
    if rootU == rootV:
        return  // Already in the same component
        
    if rank[rootU] < rank[rootV]:
        parent[rootU] = rootV
    else if rank[rootV] < rank[rootU]:
        parent[rootV] = rootU
    else:
        parent[rootV] = rootU
        rank[rootU] += 1

6. Path Compression Mechanics

When executing findParent(node), we traverse upwards from the node to its ultimate parent. Path compression ensures that every node encountered along this traversal path has its parent pointer directly reassigned to the ultimate parent.

Recursive Flow Walkthrough (Path Compression)

Consider nodes 5 -> 4 -> 3 -> 2 -> 1 where 1 is the ultimate boss. When calling findParent(5):

As the recursion unwinds, parent pointers are updated directly:

parent[2] = 1
parent[3] = 1
parent[4] = 1
parent[5] = 1

Result: The tree flattens completely, transforming a linear chain into a star graph where all nodes point directly to the boss.

7. Step-by-Step Evolution: Union by Size

Instead of maintaining ranks (which can become imprecise due to path compression), Union by Size tracks the exact number of nodes (size) in each component tree.

Initial Configuration Arrays

• parent Array: Initialized such that every node is its own parent (parent[i] = i).
• size Array: Initialized to 1 for all nodes (size[i] = 1), since every node starts as an independent component of size 1.

Comparison: Union by Rank vs. Union by Size

8. Complete C++ Production Implementation

Below is a robust, production-ready C++ implementation supporting both one-based and zero-based indexing graphs, incorporating Path Compression and Union by Size / Union by Rank.

#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
    vector<int> rank, parent, size;
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }

    int findUPar(int node) {
        if (node == parent[node])
            return node;
        // Path compression
        return parent[node] = findUPar(parent[node]);
    }

    void unionByRank(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }

    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

int main() {
    DisjointSet ds(7);
    ds.unionBySize(1, 2);
    ds.unionBySize(2, 3);
    ds.unionBySize(4, 5);
    ds.unionBySize(6, 7);
    ds.unionBySize(5, 6);
    
    if (ds.findUPar(3) == ds.findUPar(7)) {
        cout << "Same component\n";
    } else {
        cout << "Not same component\n";
    }

    ds.unionBySize(3, 7);

    if (ds.findUPar(3) == ds.findUPar(7)) {
        cout << "Same component\n";
    } else {
        cout << "Not same component\n";
    }
    return 0;
}

9. Real-World Practical Pitfalls & Edge Cases

• Mixing Union Strategies: Never combine Union by Rank and Union by Size in the same DSU instance, as their internal array states and heuristics conflict. Choose one strategy per object instantiation.
• Index Out of Bounds: Ensure the DSU arrays (parent, rank, size) are appropriately sized (n + 1 for 1-based indexing graphs; n for 0-based indexing graphs).
• Redundant Union Checks: Always verify if findUPar(u) == findUPar(v) before performing union operations to prevent incorrect rank or size increments.

10. Summary and Key Takeaways

• Disjoint Set Data Structure is an advanced graph data structure designed to manage disjoint sets and dynamically answer connectivity queries in nearly constant time.
• Two Core Operations: findParent (finds ultimate root/boss) and union (merges two components).
• Union by Rank attaches trees by comparing ranks (depths), keeping trees shallow.
• Union by Size tracks component node counts and is often considered more intuitive for beginners.
• Path Compression optimizes findParent by flattening trees during traversal, directly linking visited nodes to the ultimate parent.
• Time Complexity: With path compression and union by rank/size, both operations run in $\mathcal{O}(4\alpha)$ time, which is practically $\mathcal{O}(1)$ (constant time).
• Reusable Snippet: Encapsulating DSU logic inside a clean C++ class allows seamless reuse across diverse graph algorithms and interview problems (e.g., Kruskal's Minimum Spanning Tree).