Quick Union vs Quick Find: Union-Find Optimization Techniques Explained with Examples

Union-Find (also known as Disjoint Set Union or DSU) is a classic data structure that helps efficiently manage a collection of disjoint sets. It is widely used in algorithms involving connectivity, graph theory, and network design. Two fundamental techniques for implementing Union-Find are Quick Find and Quick Union. While both serve the same purpose—determining whether two elements are connected and merging sets—they differ significantly in performance and design. This article explains Quick Find vs Quick Union with detailed examples, Python implementations, and visual diagrams.

Understanding Union-Find

Union-Find supports two primary operations:

• Find(x): Determine which set element x belongs to. Useful for checking connectivity.
• Union(x, y): Merge the sets containing elements x and y.

For example, in graph problems like detecting cycles, connected components, or implementing Kruskal’s Minimum Spanning Tree algorithm, Union-Find is indispensable.

Quick Find Approach

In Quick Find, we maintain an array id[] where each index represents an element and the value at that index represents the set it belongs to. Two elements are connected if they share the same id.

Quick Find Characteristics

• Find operation: Very fast (O(1)) since it just checks id[p].
• Union operation: Slow (O(n)) since merging requires updating all entries of one set.
• Best used when: The application involves many find queries but fewer union operations.

class QuickFind:
    def __init__(self, n):
        self.id = list(range(n))
    
    def find(self, p):
        return self.id[p]
    
    def union(self, p, q):
        pid, qid = self.id[p], self.id[q]
        for i in range(len(self.id)):
            if self.id[i] == pid:
                self.id[i] = qid

Example: Suppose we initialize 10 components (0 to 9). After performing union(0, 1) and union(1, 2), elements 0, 1, and 2 belong to the same set.

Quick Union Approach

Quick Union uses a tree-like structure, where each element points to its parent. If an element points to itself, it is the root (or representative) of its set.

Quick Union Characteristics

• Find operation: Potentially slow (O(h)) where h is the height of the tree.
• Union operation: Relatively faster since only root changes are needed.
• Best used when: With additional optimizations like path compression and union by rank it becomes efficient.

class QuickUnion:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def root(self, i):
        while i != self.parent[i]:
            i = self.parent[i]
        return i
    
    def find(self, p):
        return self.root(p)
    
    def union(self, p, q):
        rootP = self.root(p)
        rootQ = self.root(q)
        self.parent[rootP] = rootQ

Example: If we connect union(3, 4) and union(4, 9), all three nodes (3, 4, 9) share the same root.

Quick Find vs Quick Union: Performance Comparison

Optimizations for Quick Union

While Quick Union is better than Quick Find in many scenarios, it can still degenerate into tall trees causing slow queries. Two classic optimizations are:

• Path Compression: Flatten the tree by pointing nodes directly to the root during find(). This drastically reduces tree height.
• Union by Rank/Size: Always attach the smaller tree under the larger one to keep the tree balanced.

After path compression, nodes directly link to the root, reducing height:

Python Implementation of Optimized Union-Find

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]
    
    def union(self, x, y):
        rootX, rootY = self.find(x), self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

With path compression and union by rank, both find and union operations achieve nearly constant time complexity O(α(n)), where α is the inverse Ackermann function, which grows extremely slowly.

When to Use Quick Find vs Quick Union

• Use Quick Find if your application requires many find operations and very few union operations.
• Use Quick Union with optimizations for large-scale problems involving thousands of unions and finds, such as graph connectivity or clustering problems.

Conclusion

Choosing between Quick Find and Quick Union boils down to understanding their performance characteristics. While Quick Find is intuitive but inefficient for unions, Quick Union—when combined with path compression and union by rank—is the clear winner for scalable, high-performance applications. Mastering both implementations is essential for competitive programming, algorithm design, and solving complex connectivity problems.