Union-Find: Disjoint Set Data Structure

Union-Find (also called Disjoint Set Union or DSU) is a data structure that tracks a collection of disjoint sets. It supports two operations: find (which set contains this element?) and union (merge two sets). With path compression and union by rank, both operations achieve nearly O(1) amortized time.

Union-Find powers Kruskal’s MST algorithm, detects cycles in graphs, finds connected components, and solves many partitioning problems.

Introduction

Union-Find (also called Disjoint Set Union or DSU) is a data structure that tracks a collection of disjoint sets, supporting two operations: find—which set contains this element?—and union—merge two sets together. What makes it work is that with two simple optimizations, both operations achieve amortized O(α(n)) time, where α(n) is the inverse Ackermann function that grows so slowly it is effectively constant for all practical inputs. This near-constant time makes Union-Find one of the most practical data structures for graph algorithms and connectivity problems.

The power of Union-Find comes from its simplicity and versatility. It forms the backbone of Kruskal’s minimum spanning tree algorithm, where cycle detection during edge addition requires efficient connectivity queries. It finds connected components in graphs, detects cycles, and solves partitioning problems in social networks and image processing. The data structure is also easy to implement correctly—many developers get it wrong without path compression or union by rank, leaving significant performance on the table.

This guide covers the core operations with path compression and union by rank, explains why these optimizations give near-constant time, and walks through practical applications like counting connected components, Kruskal’s MST, and the “most stones removed” problem. You’ll also see when to use union by size instead of union by rank, and how to implement find iteratively to avoid recursion depth issues.

Basic Implementation

class UnionFind:
    """
    Union-Find with path compression and union by rank.
    Nearly O(1) amortized for both operations.
    """

    def __init__(self, n):
        self.parent = list(range(n))  # Parent pointer
        self.rank = [0] * n  # Approximate tree depth

    def find(self, x):
        """
        Find root with path compression.
        Flattens tree along the way for future speedups.
        """
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Recursive compression
        return self.parent[x]

    def union(self, x, y):
        """
        Union by rank: attach smaller tree under larger tree.
        Returns True if merged, False if already in same set.
        """
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False  # Already in same set

        # Union by rank: attach smaller depth tree under larger
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x  # Ensure root_x has >= rank

        self.parent[root_y] = root_x

        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

        return True

    def connected(self, x, y):
        """Check if two elements are in the same set."""
        return self.find(x) == self.find(y)

    def count(self):
        """Count number of distinct sets."""
        return sum(1 for i in range(len(self.parent)) if self.parent[i] == i)

Optimized Operations

class OptimizedUnionFind:
    """
    Union-Find with:
    - Path compression (find)
    - Union by rank (union)
    - Size tracking
    """

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n  # Track component sizes

    def find(self, x):
        """Find with iterative path compression."""
        root = x
        while self.parent[root] != root:
            root = self.parent[root]

        # Compress path
        while self.parent[x] != root:
            next_x = self.parent[x]
            self.parent[x] = root
            x = next_x

        return root

    def union(self, x, y):
        """Union by size: attach smaller tree under larger."""
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False

        # Attach smaller size tree under larger
        if self.size[root_x] < self.size[root_y]:
            root_x, root_y = root_y, root_x

        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]

        return True

    def component_size(self, x):
        """Get size of component containing x."""
        return self.size[self.find(x)]

    def max_component_size(self):
        """Largest component size."""
        return max(self.size)

Common Applications

# Number of connected components in graph
def count_connected_components(n, edges):
    """Count components using union-find."""
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.count()


# Detect cycle in undirected graph
def has_cycle(n, edges):
    """Detect if graph has a cycle."""
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):
            return True  # Already connected = cycle
    return False


# Kruskal's MST using union-find
def kruskal_mst(n, edges):
    """
    MST using Kruskal's algorithm.
    edges: list of (weight, u, v)
    """
    # Sort edges by weight
    edges.sort(key=lambda x: x[0])

    uf = UnionFind(n)
    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) == n - 1:  # MST has n-1 edges
            break

    return mst, total_weight


# Most stones removed (LeetCode 947)
def remove_stones(stones):
    """
    Maximum stones that can be removed = total stones - number of components.
    Use union-find on stone positions.
    """
    uf = UnionFind(20000)  # 0-9999 for row, 10000-19999 for col

    for x, y in stones:
        uf.union(x, 10000 + y)  # Connect row x to column y

    # Count distinct roots
    roots = set(uf.find(x) for x, _ in stones)
    return len(stones) - len(roots)


# Longest consecutive sequence (LeetCode 128)
def longest_consecutive(nums):
    """
    Find longest consecutive sequence length.
    Use union-find to group consecutive numbers.
    """
    if not nums:
        return 0

    uf = UnionFind(len(nums))
    num_to_idx = {num: i for i, num in enumerate(nums)}

    # Union each number with its neighbor if it exists
    for num in nums:
        if num - 1 in num_to_idx:
            uf.union(num_to_idx[num], num_to_idx[num - 1])
        if num + 1 in num_to_idx:
            uf.union(num_to_idx[num], num_to_idx[num + 1])

    # Find largest component size
    max_size = 0
    for i in range(len(nums)):
        if uf.find(i) == i:
            max_size = max(max_size, uf.size[i])

    return max_size

Time Complexity Analysis

Operation	Naive	With Path Compression	With Both Optimizations
find	O(n)	O(log n)	α(n) ≈ O(1)
union	O(n)	O(log n)	α(n) ≈ O(1)
connected	O(n)	O(log n)	α(n) ≈ O(1)

α(n) is the inverse Ackermann function, which grows so slowly that for all practical values of n, α(n) ≤ 4.

Why Path Compression and Union by Rank Work

# Without optimizations: tree can degenerate to linked list (O(n) operations)

# With path compression:
# find(1) → 1 → 3 → 5 (find root)
# After: parent[1]=5, parent[3]=5, parent[5]=5 (flattened)

# With union by rank:
# Always attach smaller tree under larger
# Tree height ≤ log(n) because each merge at least doubles size of one component

Union-Find With Path Compression and Rank

These two tricks solve different problems. Path compression keeps trees short by making every find rewire nodes directly to the root. Union by rank prevents bad merges by always attaching the shallower tree under the deeper one. Use both and operations run in amortized O(1); skip one and you’re back to O(n).

The diagram below shows the transformation. The “Before” and “After” sections illustrate path compression on a chain of 5 nodes. The Union by Rank section shows how trees organize by height. Trace through each step and the mechanics should click.

graph TD
    subgraph Before["Before Path Compression (find 1)"]
        direction TB
        N1["1"]
        N2["2"]
        N3["3"]
        N4["4"]
        N5["5"]

        N1 --> N2
        N2 --> N3
        N3 --> N4
        N4 --> N5

        N5Style["5 is root"]
    end

    subgraph After["After Path Compression"]
        direction TB
        A1["1"]
        A2["2"]
        A3["3"]
        A4["4"]
        A5["5"]

        A1 -.-> A5
        A2 -.-> A5
        A3 -.-> A5
        A4 -.-> A5
        A5["5 (root)"]
    end

    subgraph UnionByRank["Union by Rank Example"]
        direction LR
        R1["rank=2, size=4"]
        R1 --> R2["rank=1, size=2"]
        R1 --> R3["rank=1, size=1"]
        R1 --> R4["rank=0"]

        R5["Attach smaller under larger"]
    end

When to Use Union-Find

Problem	Union-Find Use
Kruskal’s MST	Detect cycles while adding edges
Connected components	Group related items
Cycle detection	Check if edge connects nodes in same component
Network connectivity	Is x connected to y?
Image processing	Connected components in pixels
Clustering	Group similar items

Production Failure Scenarios

1. Path compression skipped in recursive find: If you implement find recursively but forget the assignment self.parent[x] = self.find(self.parent[x]), path compression never happens. The tree degrades to O(n) height over time. Even iterative implementations can miss path compression if the compression loop doesn’t update all nodes along the chain. Every find must flatten—test this with a long chain before deployment.

2. Union by rank/size not applied consistently: If you sometimes union with arbitrary ordering instead of by rank or size, the tree height bound breaks. A sequence of unions in bad order produces a linear chain, turning near-O(1) operations into O(n). This is especially insidious because it works fine on small test cases but degrades on large inputs.

3. Rank overflow with large n: The rank field is typically a small integer. If you have millions of elements and keep merging trees of equal rank, rank can overflow an 8-bit or 16-bit integer. The tree still works but the rank comparison logic breaks, potentially causing incorrect unions.

4. Parent array not initialized for all elements: When using union-find in a dynamic context (adding elements after initialization), new elements need proper parent and rank initialization. If you skip this, find on uninitialized elements reads garbage from the arrays and corrupts the structure.

Observability Checklist

Track union-find operations to catch degradation and correctness issues.

Core Metrics

These metrics give you a baseline for what healthy union-find behavior looks like. Track them continuously in production so you have reference points when something goes wrong. Without baseline data, anomalies are hard to spot.

• find operation count and latency per call: Record how many find calls your application makes per second and how long each takes. In a healthy system, find latency stays under a few microseconds. A spike indicates deeper trees.
• union operation count and merge rate: Count unions and track how often they actually merge (as opposed to finding already-connected elements). Merge rate dropping toward zero means most unions are no-ops. Either your graph is fully connected or something is wrong.
• Tree depth distribution across all roots: Sample this periodically. With path compression and union by rank, depth should stay below 10 even for millions of elements. If you are seeing depths climbing toward log₂(n), something is broken.
• Rank distribution across all elements: Ranks should cluster in the low single digits. A rank value above 20 for n < 1 million suggests rank overflow or incorrect rank updates.
• Component count over time: In a graph that grows over time, component count should decrease as edges are added. If it plateaus while your graph is still sparse, unions may be silently failing.

Health Signals

Health signals are the warning signs that precede a full outage. They let you catch degradation before it affects users. Set up monitoring to alert when these conditions appear, and have runbooks ready for each scenario.

• find latency increasing: tree height growing beyond log n — This is the clearest signal that path compression has stopped working or union by rank is producing unbalanced merges. Check whether your find implementation actually reassigns parent pointers on every call.
• Union merge rate dropping: all unions are between same-set elements (may indicate logic error) — A merge rate near zero when your graph is still sparse means your union logic may be rejecting valid merges. Common causes: element indices swapped, off-by-one errors in parent array access, or edges arriving in an order that happens to create no new connections.
• Rank values growing beyond log₂(n): union-by-rank broken — With proper union by rank, the maximum rank stays well below log₂(n). If ranks are climbing toward n, the rank comparison is likely skipped or inverted somewhere in your code.
• Component count not decreasing as expected: union operations failing silently — If component count stays flat while you’re processing new edges, unions may be failing without throwing exceptions. Add a counter that increments only on successful merges and correlate it with your input edge rate.
• find returning unexpected values: parent array corrupted — This is a data corruption signal. Possible causes: out-of-bounds array access writing garbage, concurrent modification without locking, or integer overflow in parent indices. Treat this as a P0 incident.

Alerting Thresholds

Set these thresholds based on your specific n and workload. The numbers below are starting points for typical applications. Adjust upward if your elements are in the tens of millions. Alerting on these conditions gives you early warning before the system becomes unusable.

• find latency > log₂(n) consistently: tree degradation — Calculate log₂(n) for your element count. For n = 1 million, log₂(n) ≈ 20. If find latency exceeds this value for more than 5% of calls over a 5-minute window, something is wrong with path compression, union by rank, or both. Check whether your find operation actually updates parent pointers on every call.
• Rank values exceeding 30 for n < 10⁶: rank tracking error — With correct union by rank, a tree of rank r has at least 2^r elements. For n < 1 million (2²⁰), rank should never exceed 20. If you’re seeing rank > 30, the rank comparison is being bypassed somewhere or you’re tracking rank in the wrong array.
• union returning False rate > 50% without actual cycles: logic error — If more than half your unions return False and you know the graph doesn’t have that many cycles, the problem is likely in how you’re mapping elements to indices or how edges are being deduplicated before reaching union.
• Component count stable when it should be changing: union not executing — When processing new edges that should be merging components, component count should decrease. If it stays flat, unions are being skipped. Common culprit: calling find on one element and union on another without checking whether they share a root first.

Distributed Tracing

Union-find calls are fast enough to disappear into network latency in distributed systems. But that speed also means problems hide until they compound. Bad merge ordering, skewed element distributions, and memory pressure all manifest as taller trees before they cause visible slowness. Tracing helps you catch the regression early.

For find, record the path length (how many parent hops to reach the root) and the compression ratio (how many nodes were re-parented). A path length near log2(n) means union by rank is holding but path compression is not doing much. Compression ratio tells you how aggressively flattening is happening; it climbs over time as the structure settles.

For union, attach the sizes of both components to the span. Merging a size-1 into a size-million is trivial; merging two size-millions triggers a rank bump and potential height growth. If you see lots of same-size merges, your element distribution might be too even for rank-based merging to help.

Useful span fields: root_node, path_length, compression_ratio, component_size_a, component_size_b, rank_delta. Tag by operation type so you can filter in your tracing UI. On slow find spans, include a hash of the parent chain so you can reconstruct which tree shape caused the problem.

• Trace each find with path length and nodes visited
• Include root node and compression ratio in span metadata
• Track union with merged component sizes
• Correlate slow finds with specific tree shapes (deep chains)

Security Notes

Union-find has specific security concerns when attacker controls operations.

Rank manipulation to cause worst-case performance: An attacker who controls union order can craft sequences that violate the union-by-rank guarantee, creating deep trees. While find is still O(log n), the constant factor matters under heavy load.

Fix: Use randomized union by shuffling operations if adversarial. Or use union by size which is harder to manipulate predictably.

Parent array corruption via overflow: If the parent array stores indices and an attacker can trigger index overflow (through large n values), the structure can be corrupted to point to arbitrary memory locations.

Fix: Validate n against maximum bounds before initialization. Use language-level bounds checking where available.

Cycle detection bypass via timing: In cycle detection contexts, if timing differences in find operations reveal tree structure, an attacker could use this to craft “safe” edges that actually create cycles but appear safe by timing.

Fix: Ensure find operations take constant time regardless of path length. Use branchless implementations to eliminate timing side channels.

Quick Recap Checklist

• Union-Find tracks disjoint sets efficiently
• find(x): returns root of set containing x
• union(x, y): merges sets containing x and y
• Path compression flattens tree on find
• Union by rank attaches smaller tree under larger
• Amortized O(α(n)) ≈ O(1) per operation
• Used in Kruskal’s MST, cycle detection, connected components

Trade-off Analysis

Approach	find Complexity	union Complexity	Space	Notes
Naive	O(n)	O(n)	O(n)	No optimizations
Path Compression Only	O(log n)	O(log n)	O(n)	Flattening on find
Union by Rank Only	O(log n)	O(log n)	O(n)	Height bound log n
Both Optimizations	α(n) ≈ O(1)	α(n) ≈ O(1)	O(n)	Inverse Ackermann
Union by Size	O(log n)	O(log n)	O(n)	Same as rank
Weighted Quick-Union	O(n) worst	O(log n)	O(n)	Without path compression

When to Prefer Each

The table above shows the tradeoffs, but the decision depends on your specific access patterns. In practice, use both optimizations unless you have a specific reason not to. Each variant exists because it serves a particular use case better.

• Path compression only: Good when unions are rare and finds are frequent. Without rank-based merging, tree height can grow to O(n) in the worst case if unions keep attaching large trees under small ones. The find operation compensates by flattening on every call, but the first find on a deep chain still takes O(n). Use this when your workload is read-heavy (like a cache that rarely invalidates) and you want the simplest optimization that helps.

• Union by rank only: Good when finds and unions are balanced. Without path compression, tree height stays bounded by log₂(n) because each merge at least doubles the size of one component. The problem is that without flattening, repeated finds on the same element still traverse the full chain. This variant works when you have balanced operations but want a simpler implementation than the full standard version.

• Both (standard): Best overall performance for most use cases. This is the textbook combination and what you should reach for by default. Path compression flattens the tree on every find, and union by rank keeps tree height near constant. Together they achieve amortized O(α(n)) per operation, which is effectively O(1) for any realistic input size. If you’re unsure, start here.

• Union by size: Better when you need component size tracking. The height bound is the same as union by rank (O(log n)), but you gain the ability to query component sizes in O(1). This matters in problems like “number of islands” or “largest connected component” where size queries happen alongside merges. The tradeoff is a slightly more complex union operation that updates the size array on every merge.

• Weighted quick-union: Legacy approach, path compression superior. This is the historical baseline from the early union-find literature. Without path compression, find is O(log n) at best and O(n) at worst. The “weighted” part (attaching smaller tree under larger) is what union by rank replicates. Use weighted quick-union only when studying historical implementations or working with legacy code that can’t be modified.

Interview Questions

Further Reading

• CLRS Chapter 21: Data Structures for Disjoint Sets — The canonical textbook treatment with formal proofs
• CP-Algorithms: Union-Find — Practical implementation variants and applications
• Visualgo: Union-Find — Interactive visualization of union-find operations
• LeetCode Union-Find Problems — Practice problems categorized by difficulty
• Kruskal’s Algorithm — Union-Find’s primary application in MST finding
• Ackermann Function — Understanding why α(n) is effectively constant

Conclusion

Union-Find gives you near-constant time set operations—find and union both run in O(α(n)), which is effectively O(1) for any practical input size. Path compression flattens the tree on each find, and union by rank keeps trees shallow. It’s the standard tool for cycle detection in Kruskal’s MST, grouping connected components, and any problem involving disjoint sets. For graph traversal basics, see Graphs: Adjacency List and Matrix, or Topological Sort for another graph ordering algorithm.