Union-Find - Recursion Causes StackOverflow in Production

Distributed systems crash, social networks grow to billions of edges, and compilers resolve symbol dependencies — all of these lean on one elegant primitive: the ability to track which elements belong to the same connected component and merge components together efficiently. Union-Find (also called Disjoint Set Union, or DSU) is the structure that makes this possible in near-constant time, and it shows up everywhere from Kruskal's minimum spanning tree algorithm to LeetCode hard problems to production network topology managers.

The naive solution to connectivity is a hash map or a boolean matrix — mark which nodes are connected and do a BFS every time you're asked a query. That works for toy problems. The moment your graph has millions of nodes and you're doing hundreds of thousands of union and find operations, that approach collapses. Union-Find solves the problem by maintaining a forest of trees where each tree represents one connected component, and two killer optimisations — path compression and union by rank — bring the amortised cost of each operation to effectively O(α(n)), where α is the inverse Ackermann function. For any input you'll encounter in the real world, α(n) ≤ 5. It's as close to O(1) as a non-trivial algorithm gets.

By the end of this article you'll be able to implement a production-grade Union-Find from scratch, explain exactly why path compression and union by rank work together (not just that they do), detect cycles in undirected graphs, build the skeleton of Kruskal's MST, and dodge the three most common bugs that trip up experienced engineers in interviews and on the job.

What is Union-Find (Disjoint Set Union)? — Plain English

Union-Find (also called Disjoint Set Union, DSU) is a data structure that tracks a set of elements partitioned into disjoint groups. It supports two core operations: find (which group does element x belong to?) and union (merge the groups of x and y).

Real-world uses: Kruskal's MST algorithm, detecting cycles in a graph, network connectivity problems (are computers A and B in the same network?), and clustering algorithms.

Naive implementation uses an array where parent[i] = i's direct parent. Find walks up the tree to the root. Two optimizations make it nearly O(1): path compression (flatten the tree during find) and union by rank (attach the smaller tree under the larger).

How Union-Find (Disjoint Set Union) Works — Step by Step

Initialization: 1. parent[i] = i for all i (each element is its own root). 2. rank[i] = 0 for all i.

Find with path compression (amortized O(alpha(n)) ≈ O(1)): 1. If parent[x] == x: return x (x is the root). 2. parent[x] = find(parent[x]) (path compression: directly connect x to root). 3. Return parent[x].

Union by rank (O(1)): 1. Find root of x: rx = find(x). 2. Find root of y: ry = find(y). 3. If rx == ry: already in same set, return False. 4. Attach smaller rank tree under larger: if rank[rx] < rank[ry]: swap rx,ry. 5. parent[ry] = rx. If rank[rx]==rank[ry]: rank[rx]++. 6. Return True.

With both optimizations: effectively O(alpha(n)) per operation where alpha is the inverse Ackermann function — practically constant.

Before and After: Path Compression Effect — Visual Diagram

Path compression is the most impactful optimisation in Union-Find. Without it, a series of unions can create a deep chain — finding the root of the last element means traversing every ancestor. With path compression, each find operation flattens the tree so that subsequent finds on any of those nodes become O(1). The diagram below shows the parent array before and after a single find(3) on a chain of four nodes. Note how nodes 1, 2, and 3 all point directly to root 0 after compression.

Worked Example — Tracing the Algorithm

Elements: 0, 1, 2, 3, 4. Initially each is its own group. parent = [0, 1, 2, 3, 4]

union(0, 1): find(0)=0, find(1)=1. Different groups. parent[1]=0. rank[0]=1. parent = [0, 0, 2, 3, 4]

union(2, 3): find(2)=2, find(3)=3. parent[3]=2. rank[2]=1. parent = [0, 0, 2, 2, 4]

union(0, 2): find(0)=0, find(2)=2. rank[0]=rank[2]=1. Attach 2 under 0. rank[0]=2. parent = [0, 0, 0, 2, 4]

find(3): parent[3]=2. parent[2]=0. Path compress: parent[3]=0. Return 0. parent = [0, 0, 0, 0, 4] (3 now points directly to root 0)

find(1): parent[1]=0. Return 0. find(3)=0. Same group! Group containing {0,1,2,3}: root=0. Group {4}: root=4.

Implementation

find uses recursive path compression: each node on the path from x to its root is made to point directly to the root. union attaches the lower-rank root under the higher-rank root; equal ranks increment the winner's rank. components tracks the number of disjoint sets and decrements on each successful union. connected simply compares the roots of two nodes.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * n
        self.components = 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):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False  # already connected
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        self.components -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3); uf.union(0, 2)
print('0 and 3 connected:', uf.connected(0, 3))  # True
print('0 and 4 connected:', uf.connected(0, 4))  # False
print('Components:', uf.components)

C++ Implementation with Iterative Find

In production C++ code, iterative find is strongly preferred over recursion to avoid stack overflow. The implementation below uses a while loop for path compression and an integer array for rank. Note the use of std::vector for dynamic sizing.

#include <vector>

class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 0), components(n) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int x) {
        // iterative find with path compression
        int root = x;
        while (parent[root] != root)
            root = parent[root];
        // compress path
        while (x != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    bool union_sets(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) std::swap(rx, ry);
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        components--;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
    int get_components() const { return components; }

private:
    std::vector<int> parent;
    std::vector<int> rank;
    int components;
};

Weighted DSU — Tracking Edge Weights in a Disjoint Set

Standard Union-Find tracks connectivity but not extra information. A weighted DSU variant stores additional data per component, such as sum of edge weights, number of nodes, or aggregated statistics. This is useful when you need to answer queries like “What is the total weight of edges in the component containing node v?” or “Maximum value in the component?”.

The core idea: store an array weight or value per root, and when merging components, combine the values. For example, to track total weight of edges added to each component, increment the root's weight by the edge weight on each union. The query component_weight(x) simply returns weight[find(x)].

class WeightedDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n          # component size (union by size)
        self.total = [0] * n         # total weight per component (root only)
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y, weight=0):
        """Merge components of x and y, adding 'weight' to the merged component's total."""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            # already connected, but still add weight (if tracking cumulative edge weight)
            self.total[rx] += weight
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        # combine totals: the old total of ry is already in self.total[ry], add to rx
        self.total[rx] += self.total[ry] + weight
        self.components -= 1
        return True

    def component_total(self, x):
        return self.total[self.find(x)]

# Example: building a weighted graph, track total weight per component
dsu = WeightedDSU(5)
dsu.union(0,1,10)   # edge weight 10
print(dsu.component_total(0))  # 10
dsu.union(2,3,20)
dsu.union(0,2,5)    # merge components with an edge weight 5
print(dsu.component_total(0))  # 10 + 20 + 5 = 35

Cycle Detection in an Undirected Graph Using Union-Find

Union-Find provides a clean linear-time algorithm for cycle detection in undirected graphs. Process each edge (u, v): find roots of u and v. If they are the same, a cycle exists (u and v are already connected). Otherwise, union them. If no edge produces same-root after all edges, the graph is acyclic.

Complexity: O(E * α(V)) — near-linear. This is used inside Kruskal's MST to skip edges that would create cycles.

Kruskal's Minimum Spanning Tree Algorithm

Kruskal's algorithm finds a minimum spanning tree for a weighted undirected graph: 1. Sort all edges by weight. 2. Initialise Union-Find with V components. 3. For each edge (u, v, w) in sorted order: - If find(u) != find(v): add edge to MST, union(u, v). - If MST size reaches V-1, stop.

Complexity: O(E log E) for sorting + O(E α(V)) for Union-Find. Union-Find makes the cycle detection O(1) per edge.

def kruskal_mst(vertices, edges):
    """
    edges: list of (weight, u, v)
    returns: list of edges in MST, total weight
    """
    edges.sort()  # sort by weight
    uf = UnionFind(vertices)
    mst = []
    total_weight = 0
    for weight, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
            if len(mst) == vertices - 1:
                break
    return mst, total_weight

Understanding O(α(n)) — The Inverse Ackermann Complexity

When both path compression and union by rank are used, the amortised time per operation is O(α(n)), where α is the inverse Ackermann function. The Ackermann function A(m, n) grows extremely fast — far faster than exponential or tower functions. Its inverse α(n) is the number of times you must apply the logarithm function (base 2) to reduce n to a constant. For all practical values of n, α(n) ≤ 5. In fact, α(n) exceeds 5 only when n > 2^65536, a number astronomically larger than the number of atoms in the observable universe. Thus, for any real‑world dataset, Union‑Find operations run in effectively constant time.

Practice Problems for Union-Find

Sharpen your Union-Find skills with these carefully chosen coding problems. They cover fundamental connectivity, cycle detection, and advanced applications.

Start with LeetCode 684 and 200 to solidify the basics, then move to the hard problems for advanced DSU patterns.

Advantages and Disadvantages of Union-Find

Union-Find is a powerful and elegant data structure, but it's not a silver bullet. Below we summarize its strengths and limitations.

In summary, Union-Find excels at dynamic connectivity problems in undirected graphs where the primary operations are union and find. For static graphs, a simple BFS/DFS might be faster. For directed graphs or queries involving paths, other data structures are needed.