Union-Find (Disjoint Set)

1. Introduction: The Ultimate Grouping Tool

Imagine you are building a social network. You have 1 million users.

• User A friends User B.
• User C friends User D.
• User B friends User C.

If I ask, "Are User A and User D in the same friend group?", how do you answer? You could build a Graph and run Breadth-First Search (BFS) from A to see if you reach D. That takes $O(V + E)$ time. If I ask 100,000 times, the server crashes.

We need a data structure explicitly designed to handle Dynamic Connectivity. We need to merge groups instantly (Union) and check if two elements are in the same group instantly (Find). This is the Union-Find (or Disjoint Set) data structure. It solves this problem in amortized $O(1)$ time.

2. Core Concept: The Representative (Root)

In Union-Find, we assign a "Boss" or "Root" to every group. If User A, B, and C are in a group, one of them (let's say A) is the Boss. To check if two people are in the same group, we just ask: "Who is your Boss?" If find(User C) == find(User D), they are in the same group!

We model this using a simple integer array parent[]. Initially, every node is its own Boss: parent[i] = i. When we Union(A, B), we find the Boss of A, find the Boss of B, and make one Boss point to the other!

3. Advanced Code Example: The Two Optimizations

A naive Union-Find can degrade into a linked list (e.g., A points to B, B points to C, C points to D). In this worst-case scenario, find(A) takes $O(N)$ time. We fix this with two legendary optimizations:

1. Path Compression (in Find): When A searches for its Boss, once it finds the absolute top Boss (D), it rewires itself to point directly to D. The next time we call find(A), it takes $O(1)$ time!
2. Union by Rank (in Union): When merging two groups, always attach the shorter tree under the root of the taller tree. This prevents the tree from getting deep.

public class UnionFind {
    private int[] parent;
    private int[] rank; // Tracks the height of the tree
    private int count;  // Tracks the number of disconnected components

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n; // Initially, every node is its own disconnected component
        
        for (int i = 0; i < n; i++) {
            parent[i] = i; // Every node is its own boss
            rank[i] = 1;   // Initial height is 1
        }
    }
    
    // O(a(N)) ~ O(1) time
    public int find(int i) {
        if (parent[i] == i) {
            return i; // We found the absolute root Boss
        }
        
        // PATH COMPRESSION:
        // Before returning, forcefully update our parent pointer to the absolute root!
        parent[i] = find(parent[i]); 
        
        return parent[i];
    }
    
    // O(a(N)) ~ O(1) time
    public boolean union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        
        // They are already in the same group! No merge needed.
        if (rootI == rootJ) {
            return false; 
        }
        
        // UNION BY RANK:
        // Attach the smaller tree under the taller tree
        if (rank[rootI] > rank[rootJ]) {
            parent[rootJ] = rootI;
        } else if (rank[rootI] < rank[rootJ]) {
            parent[rootI] = rootJ;
        } else {
            // If they are the same height, pick one arbitrarily and increase its rank
            parent[rootJ] = rootI;
            rank[rootI]++;
        }
        
        // We successfully merged two groups, so total disconnected components decreases by 1
        count--; 
        return true;
    }
    
    public int getCount() {
        return count;
    }
}

Note: With both optimizations, the time complexity becomes $O(\alpha(N))$ where $\alpha$ is the Inverse Ackermann function. For all practical values of $N$ in the known universe, $\alpha(N) \le 4$. Therefore, it is mathematically accepted as Amortized $O(1)$.

4. Master Code Example: Number of Connected Components

Problem Statement: (LeetCode 323) You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [a, b] indicates that there is an edge between a and b in the graph. Return the number of connected components in the graph.

The Insight: We could build an adjacency list and run BFS/DFS to count islands. But with our Union-Find class, this is absurdly easy. We initialize UF with n. Every time we process an edge, we union() them. Our UF class automatically decrements count on a successful merge!

public class ConnectedComponents {
    public int countComponents(int n, int[][] edges) {
        // Instantiate the class we built above!
        UnionFind uf = new UnionFind(n);
        
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        
        return uf.getCount();
    }
}

5. Master Code Example: Redundant Connection (Cycle Detection)

Problem Statement: (LeetCode 684) In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with n nodes, with one additional edge added. Return an edge that can be removed so that the resulting graph is a tree of n nodes.

The Insight: In an undirected graph, how do we know if an edge creates a cycle? If we are about to add an edge between Node A and Node B, we first check find(A) == find(B). If they are ALREADY in the same group, it means there is already a path connecting them! Adding a new direct edge between them guarantees a cycle!

public class RedundantConnection {
    public int[] findRedundantConnection(int[][] edges) {
        // The problem states nodes are from 1 to N. We use edges.length + 1 for 1-indexing.
        UnionFind uf = new UnionFind(edges.length + 1);
        
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            
            // Try to union them. If union returns false, they were already connected!
            // This edge is the redundant cycle-causing edge.
            if (!uf.union(u, v)) {
                return edge;
            }
        }
        
        return new int[0];
    }
}

6. Common Mistakes Beginners Make

1. Forgetting Path Compression

   • The Mistake: public int find(int i) { if (parent[i] == i) return i; return find(parent[i]); }
   • Why it's wrong: You missed the parent[i] = assignment! Without it, you are traversing the tree up to the root, but you aren't fixing the pointers on the way back down. Your Find operation remains $O(N)$ worst-case.

2. Unioning the Nodes instead of the Roots

   • The Mistake: parent[j] = i; instead of parent[rootJ] = rootI;.
   • Why it's wrong: You must merge the Bosses! If you just point node j to node i, you are ripping node j away from its previous group, breaking the graph. You must find the absolute root of j and attach that root to the absolute root of i.

3. Using BFS/DFS when Union-Find is required

   • The Mistake: Using Graph Traversals for "Dynamic Connectivity".
   • Why it's wrong: If a problem involves edges being added dynamically one by one, and asking for the group status after each addition, running BFS every time takes $O(E \times (V+E))$. Union Find does it in $O(E)$.

7. Interview Q&A

Q1: Do I have to implement both Path Compression AND Union by Rank in an interview? Answer: Path Compression is mandatory because it is 1 extra line of code and provides 90% of the performance boost. Union by Rank is often skipped by candidates to save time writing code, because Path Compression alone drops the time complexity to $O(\log N)$, which is usually acceptable. However, writing both shows true mastery.

Q2: Can Union-Find be used on Directed Graphs? Answer: Generally, no. Union-Find inherently creates undirected merged pools of components. If A -> B, UF says they are in the same group. But in a directed graph, you can't necessarily reach A from B! For directed cycle detection, use Topological Sort (Kahn's) or DFS with a 3-state visited array.

8. Practice Problems

1. Number of Connected Components (LeetCode 323)
   • Goal: Master the standard template and the count variable.
2. Redundant Connection (LeetCode 684)
   • Goal: Master undirected cycle detection.
3. Accounts Merge (LeetCode 721 - Medium/Hard)
   • Hint: Highly practical problem. Use emails as nodes. Map emails to integer IDs to use the parent[] array, then run Union-Find.

9. Summary

• The Goal: Dynamic Connectivity. Grouping elements and finding cycles instantly.
• The Find: parent[i] = find(parent[i]). Path compression flattens the tree.
• The Union: parent[rootJ] = rootI. Always merge the roots, never the raw nodes.
• Complexity: Amortized $O(1)$ time.