Disjoint Set Union (Union-Find)

# CHAPTER 27

Disjoint Set Union (Union-Find) #

1. Introduction #

2. Learning Objectives #

• Define the two primary functions: Find() and Union().

• Implement a Parent tracking Array to represent Disjoint Sets.

• Execute Path Compression to optimize the Find query.

• Execute Union by Rank to optimize the Union merge.

3. The Core Concept (Sets and Representatives) #

Operation 1: Union(A, B) If we draw a physical Edge connecting Node 0 and Node 1, we must Union their Sets. We update the array so Node 1's parent is now Node 0. Parent Array: [0, 0, 2, 3, 4]. (Node 0 and Node 1 are now a connected family. Node 0 is the "Representative" boss).

Operation 2: Find(X) If we want to know what family a node belongs to, we call Find(). It climbs the Parent array until it finds the ultimate boss (a node whose parent is itself). Find(1) returns 0. Find(0) returns 0.

Cycle Detection Logic: If we pull a new Edge connecting Node A and Node B. We call Find(A) and Find(B).

• If the answers are DIFFERENT, they belong to different families. Safe to connect! Call Union(A, B)!

• If the answers are exactly the SAME, they already belong to the same family tree! Connecting them draws a line between two nodes that are already connected elsewhere... CYCLE DETECTED!

4. The Two Ultimate Optimizations #

Optimization 1: Union by Rank (Tree Balancing) We maintain a Rank (or Size) array. When calling Union(Set A, Set B), we always attach the *smaller* tree underneath the root of the *larger* tree. This mathematically guarantees the resulting tree remains shallow and balanced, keeping $O(\log N)$ search depth.

Optimization 2: Path Compression (The $O(1)$ Miracle) This is the true genius of Union-Find. When you call Find(4) and it traces 4 -> 3 -> 2 -> 1 -> Boss(0). Instead of just returning 0, the Find algorithm actively rewrites the array as it backtracks! It forcefully unplugs 4, 3, and 2, and plugs them ALL directly into Boss 0. The next time you call Find(4), it doesn't take 4 steps. It takes 1 step. The tree flattens itself dynamically as you search it!

5. Python Implementation (Production Code) #

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]  # Every node is its own boss initially
        self.rank   = [1] * size                 # Track tree depth for balancing

    # 1. The Find Function (With Path Compression)
    def find(self, i):
        if self.parent[i] == i:
            return i  # Found the Boss!
        # Recursive Path Compression — dynamically flatten the tree!
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    # 2. The Union Function (With Union by Rank)
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)

        if root_i != root_j:  # Only merge if they belong to different sets!
            # Attach smaller-rank tree under the larger-rank tree
            if self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            elif self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i  # Tie-breaker
                self.rank[root_i] += 1        # Increase height
            return True   # Successfully Unioned!
        else:
            return False  # CYCLE DETECTED! Both have the same Root!

# Test it out!
uf = UnionFind(5)
print(uf.union(0, 1))  # True  (Safe)
print(uf.union(1, 2))  # True  (Safe)
print(uf.union(0, 2))  # False — Cycle Detected! 0 and 2 are already linked!

6. The Inverse Ackermann Function #

7. Applications #

• Kruskal's MST Algorithm: Powering the rapid cycle-detection phase.

• Image Processing: Detecting isolated "blobs" or connected islands of pixels.

• Network Connectivity: Quickly checking if two computers in a massive server farm can talk to each other.

8. Common Mistakes #

• Forgetting Path Compression: When writing the recursive Find function, beginners often write return self.find(self.parent[i]). This finds the answer, but forgets to *save* it! You MUST write self.parent[i] = self.find(...) to flatten the array!

9. Exercises #

1. 1. Trace the Parent array state step-by-step for a 5-node setup doing the following: Union(0,1), Union(2,3), Union(1,3). Assume Union by Rank is used.

1. 2. What would happen to the Time Complexity of Find if you implemented Union-Find using only the basic Parent array without Path Compression or Union by Rank?

10. MCQs with Answers #

11. Interview Preparation #

• *Data Modeling:* "A server farm has 500 computers. We run a script adding cables between pairs of computers one at a time. After 300 cables are added, we want to know if Computer 12 and Computer 85 can communicate. What algorithm provides the fastest instant answer?" *(Answer: Union-Find! Set up 500 Disjoint Sets. Every time a cable is added, run Union(A, B). To check communication, simply run Find(12) == Find(85). With Path Compression, it executes in $O(1)$ time!)*

12. Summary #

13. Next Chapter Recommendation #