Disjoint Sets and Dynamic Connectivity

Introduction

Many problems in computer science ask whether two objects are connected, whether they belong to the same group, or how groups change as relationships are added. Examples include determining connected components in a network, joining clusters, constructing a minimum spanning tree, and segmenting an image into coherent regions. These problems share a common computational pattern: maintain a collection of disjoint sets while repeatedly merging sets and testing membership in the same set.

The disjoint-set data structure, also called union–find, is designed for this pattern. It supports two principal operations:

• Find(x): identify the set containing element x.
• Union(x, y): merge the sets containing x and y.

With path compression and union by rank, a sequence of m operations on n elements runs in time O(m α(n)), where α is the inverse Ackermann function. For every practical input size, α(n) is at most a very small constant. Thus union–find is effectively linear for most applications, while retaining a rigorous asymptotic guarantee.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Explain the abstract model and invariants of disjoint-set forests.
2. Implement Find and Union correctly.
3. Explain and apply path compression and union by rank or size.
4. Prove the principal time bounds and interpret the inverse Ackermann function.
5. Apply union–find to clustering, connected components, image segmentation, and minimum spanning trees.
6. Evaluate limitations involving deletions, concurrency, memory, and application-specific semantics.

1. The Disjoint-Set Abstract Data Type

Let U be a universe of n elements. A partition of U is a collection of nonempty subsets such that every element belongs to exactly one subset and no two subsets overlap. A disjoint-set structure maintains such a partition under merging.

Initially, each element is usually placed in its own singleton set:

A Union operation replaces two distinct sets A and B by their union A ∪ B. A Find operation returns a representative of the set containing a specified element. The representative is an implementation object; it has no inherent semantic meaning unless the application assigns one.

A useful equivalence relation is:

The relation is reflexive, symmetric, and transitive. Union changes the relation by adding connectivity between two previously separate classes.

Terminology

A component is one current set. A representative is the canonical identifier returned for a component. A root is a representative in the forest implementation. A link is the parent pointer from one root to another. The structure is dynamic because the partition changes during execution, although the standard structure supports additions of connections rather than arbitrary deletions.

2. Forest Representation

The most effective implementation represents each set as a rooted tree. Every element stores a parent pointer. A root is identified by the condition parent[x] = x. All elements in one tree constitute one set, and the root is its representative.

For n elements, the arrays commonly include:

The fundamental invariant is that repeatedly following parent pointers from any element eventually reaches exactly one root. Consequently, two elements are in the same set precisely when their roots are equal.

Basic Find

FIND(x):
    while parent[x] ≠ x:
        x ← parent[x]
    return x

If the tree has height h, Find takes O(h) time. Without balancing, repeated unions can create a chain of n nodes, making a Find operation O(n).

Basic Union

UNION(x, y):
    rx ← FIND(x)
    ry ← FIND(y)
    if rx = ry:
        return false
    parent[ry] ← rx
    return true

The return value is often useful: true indicates that a merge occurred, while false indicates that x and y were already connected.

3. Union by Rank and Union by Size

Union by Rank

Rank is an upper bound on the height of a tree. When two roots are joined, the root with smaller rank is made a child of the root with larger rank. If ranks are equal, either root may become the parent, and the new root’s rank increases by one.

UNION_BY_RANK(x, y):
    rx ← FIND(x)
    ry ← FIND(y)
    if rx = ry:
        return false
    if rank[rx] < rank[ry]:
        parent[rx] ← ry
    else if rank[rx] > rank[ry]:
        parent[ry] ← rx
    else:
        parent[ry] ← rx
        rank[rx] ← rank[rx] + 1
    return true

Ranks are not exact heights after path compression. They remain valid upper bounds and are used only to guide linking.

Union by Size

An alternative stores the number of nodes in each root’s tree and attaches the smaller tree to the larger tree. This has the same asymptotic performance as union by rank and is sometimes easier to interpret.

UNION_BY_SIZE(x, y):
    rx ← FIND(x)
    ry ← FIND(y)
    if rx = ry:
        return false
    if size[rx] < size[ry]:
        swap(rx, ry)
    parent[ry] ← rx
    size[rx] ← size[rx] + size[ry]
    return true

Only roots need reliable rank or size values. Values stored at nonroots are not used by the union operation.

4. Path Compression

Path compression improves Find by making every visited node point directly to the root. A recursive formulation is:

FIND(x):
    if parent[x] ≠ x:
        parent[x] ← FIND(parent[x])
    return parent[x]

Suppose the path is x → a → b → r, where r is the root. After Find(x), the pointers for x, a, and b point directly to r. Future searches through these nodes are much shorter.

Path compression changes the shape of trees but not the partition represented by the forest. It is therefore safe because the root remains the representative of the same component.

An iterative two-pass version is preferable in environments where recursion depth is restricted:

FIND_ITERATIVE(x):
    r ← x
    while parent[r] ≠ r:
        r ← parent[r]
    while parent[x] ≠ x:
        next ← parent[x]
        parent[x] ← r
        x ← next
    return r

5. Complexity Analysis

Union by Rank Alone

If union by rank is used without path compression, the height of every tree is O(log n). To see why, a node’s depth increases only when two roots of equal rank are joined. At that event, the size of the resulting tree at least doubles. Therefore a node’s depth can increase at most log₂ n times.

Thus:

• Find: O(log n) worst case.
• Union: O(log n), because it performs two Finds.
• Space: O(n).

Path Compression with Union by Rank

When both optimizations are used, the standard amortized bound for any sequence of m operations on n elements is:

Here, α(n) is the inverse Ackermann function. The Ackermann function grows so rapidly that its inverse grows extraordinarily slowly. The exact threshold values depend on the formal definition of the Ackermann function, but for all input sizes encountered in practical computing, α(n) is a small integer.

The bound is amortized, not necessarily a worst-case bound for every individual operation. A particular Find may still traverse a nonconstant path, but expensive operations make later operations cheaper. The average cost over the complete sequence is bounded by O(α(n)) per operation.

A rigorous proof uses a hierarchical analysis of ranks and charging arguments. The main structural facts are:

1. Ranks increase only when equal-rank roots are joined.
2. A root of rank r represents a tree containing at least 2ʳ elements before compression effects are considered.
3. Parent ranks increase strictly along a path from a node toward a root.
4. Path compression repeatedly moves nodes across rank levels, and the number of relevant levels is controlled by α(n).

The resulting bound is asymptotically optimal in the comparison and pointer-machine models for the standard online problem, up to constant factors in the classical formulation.

Space and Initialization

The arrays parent, rank, and size require O(n) memory. Initializing n singleton sets requires O(n) time. If the elements are arbitrary objects rather than integers, a mapping from object identifiers to array indices may be required; this mapping can add memory and expected-time costs.

6. Worked Example

Consider elements A, B, C, D, E, and F. Initially, every element is a singleton. Apply the operations:

1. Union(A, B)
2. Union(C, D)
3. Union(A, C)
4. Union(E, F)
5. Find(B)
6. Union(B, E)

Using union by rank, after the first two operations there are components {A, B}, {C, D}, {E}, and {F}. The first two trees each have rank 1. Union(A, C) joins equal-rank trees, producing {A, B, C, D} with rank 2. Union(E, F) produces {E, F} with rank 1. Finally, Find(B) returns the root of the four-element component. Union(B, E) finds the roots of {A, B, C, D} and {E, F}; the rank-2 root becomes the parent of the rank-1 root.

The final partition is:

A later Find on any element can compress its path, reducing future costs without changing this partition.

7. Applications

7.1 Connected Components in an Undirected Graph

For an undirected graph G = (V, E), initialize one set for every vertex. For each edge (u, v), perform Union(u, v). At the end, vertices u and v are in the same connected component if and only if Find(u) = Find(v).

The running time is:

The O(|V|) term accounts for initialization. This is especially useful when edges arrive incrementally and queries must be answered between arrivals.

Union–find does not directly produce shortest paths, distances, or the actual route between two vertices. For those tasks, breadth-first search, Dijkstra’s algorithm, or another graph algorithm is required.

7.2 Kruskal’s Minimum Spanning Tree Algorithm

Given a connected, weighted, undirected graph, Kruskal’s algorithm sorts edges by nondecreasing weight and scans them in that order. An edge is accepted if its endpoints are currently in different components; otherwise it is rejected because accepting it would create a cycle.

KRUSKAL(G):
    initialize one set for every vertex
    sort edges by nondecreasing weight
    T ← empty set
    for each edge (u, v) in sorted order:
        if FIND(u) ≠ FIND(v):
            add (u, v) to T
            UNION(u, v)
    return T

If G has V vertices and E edges, sorting costs O(E log E), while the union–find operations cost O(E α(V)). Therefore the total time is:

The equality follows because α(V) grows much more slowly than log E for ordinary graph sizes. The correctness of Kruskal’s algorithm follows from the cut property: a lightest edge crossing a cut can safely belong to some minimum spanning tree.

7.3 Clustering

In hierarchical or threshold-based clustering, each data point initially forms its own cluster. When a similarity or distance threshold indicates that two clusters should merge, Union combines them. Find answers whether two observations currently belong to the same cluster.

For a distance threshold τ, one possible rule is to merge points or candidate clusters when:

where d is a specified distance function and τ is chosen by the analyst. Union–find efficiently maintains cluster membership, but it does not itself determine the distance function, threshold, linkage criterion, or cluster quality. Those choices belong to the clustering model.

A common mistake is to treat union–find as a complete hierarchical clustering algorithm. It records the current partition but does not automatically preserve merge heights, dendrogram structure, centroids, or cluster statistics. Such metadata must be maintained separately.

7.4 Image Segmentation

Treat each pixel as a vertex. Connect neighboring pixels—four-neighbor or eight-neighbor adjacency are common choices—and merge neighboring pixels when their intensity, color, or learned feature distance satisfies a similarity rule. The resulting components form candidate image regions.

For pixels p and q, a simple condition might be:

where f(p) and f(q) are feature vectors and τ is a tolerance. The rule is application-dependent and must account for noise, illumination, texture, and spatial scale. Union–find is attractive because it handles millions of local merge decisions with near-constant amortized cost.

7.5 Percolation and Network Reliability

In lattice or infrastructure simulations, sites or edges are activated over time. Union–find tracks whether a connected path exists between designated boundaries or terminals. This supports experiments in percolation, resilience analysis, and incremental network monitoring. It is important to distinguish connectivity from operational capacity: a connected path may still be unusable because of bandwidth, failure probability, or flow constraints.

8. Detailed Applied Case: Incremental Road-Network Connectivity

Background

Consider an illustrative transportation agency that receives road-opening events from a construction and maintenance system. Each event declares that a previously unavailable undirected road segment has become operational. Analysts need to answer whether two towns are connected after each event.

Problem

The network contains 250,000 towns and millions of possible road events. Recomputing a graph traversal after every event would be expensive, particularly when most events connect regions that were already connected.

Analysis

The events are incremental: roads are added but not removed. This is precisely the operating model of union–find. Town identifiers are mapped to integer indices. Each road event (u, v) invokes Union(u, v). A query invokes Find(u) and Find(v) and compares the roots.

If Q events and queries are processed, the union–find work is O((N + Q) α(N)), excluding input parsing and any indexing overhead. The structure also reports whether an event joined two previously separate regions, which can support statistics about the number of connected components.

Approach and Solution

The implementation uses path compression and union by size. A separate componentCount variable is initialized to N and decremented only when Union returns true. This variable is not derived by scanning all vertices after every event.

For auditability, each event receives a sequence number and is stored in an append-only log. The log records the event, the roots before the merge, and whether a merge occurred. The union–find arrays themselves are optimized for computation, whereas the log provides an operational explanation.

Outcome

Connectivity queries execute with near-constant amortized cost. The agency can identify isolated regions, measure the number of components over time, and trigger alerts when critical towns become connected. However, if a road later closes, ordinary union–find cannot simply undo the merge. The system must use an offline reverse-time method, a rollback structure, or a dynamic-connectivity algorithm designed for deletions.

Learning Points

1. The data structure is ideal when relationships are added monotonically.
2. A computational representative should not be confused with a geographic leader.
3. Operational logs and governance metadata are separate from parent pointers.
4. Deletions fundamentally change the algorithmic problem.

9. Limitations and Design Choices

Deletions

Standard union–find supports merging but not efficient arbitrary splitting. Changing parent pointers to remove one edge may incorrectly separate other relationships that share the same component. Offline solutions sometimes process operations in reverse: deletions become additions, while a segment tree over time can handle intervals of activity. Fully dynamic connectivity generally requires more advanced structures, such as Euler-tour trees or link–cut trees, depending on the model.

Representative Semantics

The root is selected for efficiency, not meaning. Applications should not interpret the root as the oldest item, highest-priority user, or geographically central node unless the implementation explicitly enforces that policy. If a semantic leader is required, store it as separate metadata and update it during Union.

Metadata Maintenance

Cluster size, sum, minimum, maximum, label counts, or feature statistics can be stored at roots. When two components merge, their metadata must be combined using an associative operation. For example, component size uses addition:

If path compression changes parent pointers, metadata should still be maintained only at roots unless there is a compelling reason to duplicate it.

Concurrency and Distributed Systems

A simple array implementation is not automatically thread-safe. Concurrent Union operations can race while changing parent pointers or ranks. Solutions include locks, atomic compare-and-swap protocols, specialized parallel algorithms, or partitioning the workload. In distributed systems, network communication and consistency often dominate the theoretical union–find cost. A local representative is not necessarily globally stable across machines.

Memory and Identifiers

For huge datasets, array-based storage is efficient when identifiers are dense integers. Sparse or string identifiers require dictionaries or compression. Engineers should account for the memory of the identifier map, input buffers, logs, and metadata rather than reporting only the O(n) parent array.

10. Best Practices

1. Initialize every element exactly once before processing operations.
2. Always compare roots, not raw parent values, when testing connectivity.
3. Combine path compression with union by rank or size.
4. Use an iterative Find when recursion depth may be restricted.
5. Return whether Union actually merged two components.
6. Maintain component counts and root metadata explicitly.
7. Separate algorithmic representatives from application-level identities.
8. Validate whether the workload contains only additions; use another method if deletions are central.
9. Test redundant edges, singleton queries, self-unions, duplicate edges, and disconnected vertices.
10. Document whether graph edges are undirected and whether connectivity is logical, physical, or probabilistic.

11. Contemporary and AI-Related Uses

Union–find remains relevant in machine learning pipelines even when the central model is neural. It can consolidate duplicate records, form connected regions in graph-based preprocessing, group samples linked by high-confidence constraints, and post-process semantic-segmentation masks. In weak supervision, must-link constraints can be represented by unions, while cannot-link constraints require additional logic because union–find alone does not detect every incompatibility.

In large-scale data processing, batch union–find can be combined with map–reduce-style edge generation, although global merging requires careful synchronization. Differentiable learning systems generally cannot backpropagate through ordinary discrete Union operations without a relaxation or a separate optimization stage. Therefore union–find is usually a discrete preprocessing or post-processing component rather than a differentiable layer.

Governance is important when connectivity implies a consequential decision. Merging identities, customer records, medical observations, or access-control groups can propagate errors. Systems should retain provenance, confidence thresholds, correction mechanisms, and human review for high-impact cases. Efficient connectivity is not evidence that the underlying relationship is valid.

Chapter Summary

Disjoint-set structures maintain a partition of elements under repeated merges and connectivity queries. Forest representations use parent pointers, with roots acting as representatives. Union by rank or size prevents tall trees, while path compression flattens paths during Find. Together they yield an amortized complexity of O(m α(n)) for m operations on n elements, effectively constant per operation in practical settings.

Union–find is especially effective for incremental connected components, Kruskal’s minimum spanning tree algorithm, threshold clustering, image segmentation, and network simulations. Its principal limitation is the lack of efficient arbitrary deletions. Correct use also requires attention to representative semantics, metadata, concurrency, identifier management, provenance, and the distinction between computational connectivity and real-world validity.

Key Terms

Disjoint set: A collection of pairwise non-overlapping sets.

Partition: A set of nonempty subsets whose union is the entire universe and which do not overlap.

Union–find: A data structure supporting set merging and representative queries.

Find: Operation that returns the representative of an element’s set.

Union: Operation that merges two sets.

Representative: Canonical identifier for a component.

Root: Tree node whose parent is itself.

Parent pointer: Link from a node to its immediate forest ancestor.

Disjoint-set forest: Collection of rooted trees representing components.

Path compression: Find optimization that points visited nodes directly to the root.

Rank: Upper-bound height measure used to guide root linking.

Union by rank: Rule attaching the lower-rank root below the higher-rank root.

Union by size: Rule attaching the smaller component below the larger component.

Amortized analysis: Analysis of average cost over a sequence of operations.

Inverse Ackermann function: Extremely slowly growing function appearing in the union–find bound.

Connected component: Maximal set of mutually reachable vertices in an undirected graph.

Minimum spanning tree: Minimum-weight tree connecting all vertices of a connected weighted graph.

Dynamic connectivity: Maintenance of connectivity information as relationships change.

Metadata: Additional information maintained for each component, such as size or label counts.

Review Questions

Short Answer Questions

1. What invariant identifies a root in a disjoint-set forest?
2. Why does union by rank limit tree height?
3. What structural change does path compression make during Find?
4. State the amortized complexity of m union–find operations on n elements when both main optimizations are used.
5. Why can standard union–find not directly support arbitrary deletions?

Long Answer Questions

1. Explain the forest representation of disjoint sets and provide pseudocode for Find and Union by rank.
2. Compare union by rank and union by size, including their similarities, differences, and asymptotic guarantees.
3. Describe Kruskal’s algorithm and explain how union–find prevents cycle formation.
4. Explain how union–find can be used for image segmentation, including the role of adjacency and a similarity threshold.
5. Discuss the practical and governance limitations of using union–find in a large identity-resolution system.

Analytical / Application Questions

1. A graph has vertices {1, 2, 3, 4, 5, 6} and edges (1,2), (3,4), (2,3), (5,6), and (4,5). Determine the final connected components and explain the union–find operations.
2. An incremental network permits additions but no deletions. Design a procedure that reports both whether a newly added edge joins two components and the current number of components. State the time and space complexity.
3. A data pipeline requires both must-link and cannot-link constraints. Explain what union–find can enforce directly, what it cannot enforce by itself, and how you would detect a contradiction after processing must-link constraints.

Multiple Choice Questions with Answers

Question 1

Which condition identifies a root in a disjoint-set forest?

A. parent[x] = x

B. rank[x] = 0

C. size[x] = 1

D. parent[x] = null

Correct Answer: A. parent[x] = x

Question 2

What is the main purpose of path compression?

A. To increase the rank of every node

B. To make visited nodes point directly to the root

C. To store all elements in sorted order

D. To support arbitrary deletions

Correct Answer: B. To make visited nodes point directly to the root

Question 3

Using union by rank without path compression, the worst-case height is bounded by:

A. O(1)

B. O(n)

C. O(log n)

D. O(n log n)

Correct Answer: C. O(log n)

Question 4

With path compression and union by rank, m operations on n elements take:

A. O(mn)

B. O(m log n)

C. O(n²)

D. O(m α(n))

Correct Answer: D. O(m α(n))

Question 5

In Kruskal’s algorithm, an edge is accepted when:

A. It has the greatest weight

B. Its endpoints are in different components

C. Its endpoints have equal ranks

D. It connects two vertices already in the same component

Correct Answer: B. Its endpoints are in different components

Question 6

Initially, a standard disjoint-set structure places each element in:

A. One set containing all elements

B. A balanced tree with every element

C. Its own singleton set

D. A queue ordered by rank

Correct Answer: C. Its own singleton set

Question 7

If Find(u) and Find(v) return the same representative, then u and v:

A. Have equal numeric identifiers

B. Are in the same component

C. Were merged in the immediately previous operation

D. Must be adjacent in the graph

Correct Answer: B. Are in the same component

Question 8

Which operation is not efficiently supported by ordinary union–find?

A. Merging two components

B. Testing whether two elements are connected

C. Counting successful merges with a counter

D. Splitting an arbitrary component after an edge deletion

Correct Answer: D. Splitting an arbitrary component after an edge deletion

Question 9

For a graph with V vertices and E edges, the union–find work in Kruskal’s algorithm is:

A. O(VE)

B. O(E α(V))

C. O(V log V) regardless of E

D. O(2^V)

Correct Answer: B. O(E α(V))

Question 10

Why should a root not automatically be interpreted as a semantic leader?

A. Roots cannot be found efficiently

B. Root selection is determined primarily by balancing heuristics

C. Roots always change after every operation

D. Only leaves can store metadata

Correct Answer: B. Root selection is determined primarily by balancing heuristics