Union-Find and Disjoint Sets

Analogy categoryAnalogies

Introduction

The Union-Find (also called Disjoint Set Union, or DSU) data structure maintains a collection of disjoint sets and supports two operations efficiently: finding which set an element belongs to, and merging two sets together. It is the backbone of Kruskal's minimum spanning tree algorithm, cycle detection in undirected graphs, and connectivity queries in dynamic graphs where edges are only added, never removed.

🏏

Cricket analogy: Tracking which franchise a player belongs to across an IPL auction, where trades merge two franchises' rosters, is a union-find problem -- the same structure powers Kruskal's approach to building a minimum-cost fielding rotation and detecting when two players are already on the same team.

Algorithm/Syntax

python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # Path compression: point every node on the path directly to the root
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # already in the same set

        # Union by rank: attach smaller tree under larger tree's root
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True

Explanation

Each element starts as its own set, represented by a tree where every node points to a parent, and the root is the set's representative. find walks up the parent pointers to the root; path compression flattens the tree by making every visited node point straight to the root, so future lookups are faster. union merges two trees by attaching the root of the smaller-ranked tree under the root of the larger-ranked tree, keeping trees shallow. Combining path compression with union by rank gives an amortized time complexity of O(alpha(n)) per operation, where alpha is the inverse Ackermann function -- a value that grows so slowly it is less than 5 for any input size that could ever exist in practice, so it is treated as effectively O(1).

🏏

Cricket analogy: Each player starts as captain of their own one-man team; find walks up a chain of 'reports to' links to the actual captain, and path compression re-points every player directly to the captain so future lookups are instant, while union-by-rank always merges the smaller squad under the larger captain, keeping the chain nearly flat -- effectively O(1) lookups.

Example

python

def has_cycle(n, edges):
    """Detect a cycle in an undirected graph using Union-Find."""
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):
            # u and v were already connected -> adding this edge forms a cycle
            return True
    return False


def kruskal_mst(n, edges):
    """edges: list of (weight, u, v). Returns list of MST edges."""
    uf = UnionFind(n)
    mst = []
    for weight, u, v in sorted(edges):
        if uf.union(u, v):
            mst.append((weight, u, v))
    return mst


# Trace: 4 nodes, edges 0-1, 1-2, 2-3, 3-0 (this forms a cycle)
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
print(has_cycle(4, edges))  # True, because 3-0 reconnects an already-connected component

# Trace: Kruskal on a weighted graph
weighted_edges = [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3)]
print(kruskal_mst(4, weighted_edges))  # [(1, 0, 1), (2, 1, 3), (3, 1, 2)]

Complexity

With both optimizations, a sequence of m union/find operations on n elements runs in O(m * alpha(n)) time, essentially linear. Without path compression or union by rank, a naive implementation can degrade to O(n) per operation, making a sequence of operations O(n^2) in the worst case. Space complexity is O(n) for the parent and rank arrays.

🏏

Cricket analogy: Processing m trade-and-lookup operations across n players with both path compression and union-by-rank takes essentially linear O(m * alpha(n)) time; without those optimizations, a naive reporting chain could degrade to O(n) per lookup, making a full auction's operations O(n^2) overall.

Key Takeaways

Union-Find tracks disjoint sets with two core operations: find(x) and union(x, y).
Path compression flattens trees during find; union by rank keeps trees balanced during union.
Together they give near-constant amortized time per operation: O(alpha(n)).
Classic uses: cycle detection in undirected graphs and Kruskal's minimum spanning tree algorithm.
Union-Find only supports merging sets efficiently, not splitting them back apart.

Practice what you learned

1. What is the amortized time complexity of find/union with path compression and union by rank?

2. What does path compression do during a find(x) call?

3. Which classic algorithm relies on Union-Find to avoid forming cycles while selecting edges?

4. In union by rank, when merging two trees of equal rank, what happens?

Was this page helpful?

Floyd-Warshall Algorithm

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#UnionFindAndDisjointSets#Union#Find#Disjoint#Sets#StudyNotes#SkillVeris