Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Disjoint sets: merge connectivity without tracing every path

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A disjoint-set union structure partitions known elements into groups and supports find and union. Union by size attaches the smaller root under the larger; path compression shortens later find paths. Over a sequence of operations, amortized cost is O(alpha(n)) per operation, where alpha is the inverse Ackermann function and grows extremely slowly. The structure answers whether two elements are in the same component. It does not recover the actual path between them, represent directed reachability, or automatically remove an edge. The element universe and behavior for an unknown ID must be defined by the caller.

Operational case

A warehouse network has sites 0 through 3. Repairs open links 0-1 and 2-3, leaving two components. When link 1-2 opens, all four sites share a component. A connectivity dashboard can answer whether 0 and 3 are connected without walking the route map each time. If a link later closes, this DSU cannot split the group; the application must rebuild from active links or use a more complex changing-link connectivity method. This matters in operational dashboards where links can both appear and disappear.

Working Python program

python
parent = list(range(4))
size = [1] * 4

def find(site):
    while parent[site] != site:
        parent[site] = parent[parent[site]]
        site = parent[site]
    return site

def connect(left, right):
    left_root, right_root = find(left), find(right)
    if left_root == right_root:
        return
    if size[left_root] < size[right_root]:
        left_root, right_root = right_root, left_root
    parent[right_root] = left_root
    size[left_root] += size[right_root]

connect(0, 1)
connect(2, 3)
print(find(0) == find(3))
connect(1, 2)
print(find(0) == find(3))

Output

Output
False
True

Time, space, and tradeoff

Initialization uses O(n) time and space for n sites. Union and find have near-constant amortized behavior with both optimizations, but a single operation's exact path length is not literally constant. The sample uses fixed integer IDs and mutates parent links; a production wrapper should validate ID bounds. Do not use this representation alone when a caller needs a route or a historical answer at an earlier edge version. Keep active-link revision with the DSU snapshot to avoid claiming current connectivity from stale unions.

Common Mistakes

  • Do not use DSU to answer directed reachability.
  • Do not expect union to support removing an edge.
  • Do not infer an actual route from a shared root.

Connected lessons

Disjoint-set rollback: restore an earlier connectivity checkpoint extends this operation.

Parity disjoint set: maintain same-or-different constraints extends this operation contract.

Moveable disjoint sets: transfer one shipment without splitting its old tree adds a related structure with a different operation boundary.

Successor disjoint sets: skip permanently retired slots examines a related structure with a different operation boundary.

data structures
graphs-and-disjoint-sets
Storage details