Disjoint Sets

A disjoint-set structure maintains a changing partition of elements into non-overlapping groups. It answers two questions efficiently:

1. Which group contains this element?
2. Should these two groups be merged?

The structure is also called union-find after its central operations. It does not enumerate arbitrary set contents as naturally as a hash set, and it does not split a group after merging. Its strength is repeated connectivity maintenance under one-way unions.

Partition Model

A partition of a universe U is a collection of non-empty subsets such that:

• every element of U belongs to one subset;
• no element belongs to two different subsets.

For

U = {0,1,2,3,4,5,6,7}

one partition is:

{0,3,5}  {1,6}  {2}  {4,7}

The subsets cover the universe and are pairwise disjoint. The internal order of a subset has no meaning.

A disjoint-set structure usually gives each subset one representative. The representative is an implementation-selected element used as a stable answer for comparisons at that moment; it need not be the smallest, first inserted, or semantically special element.

find(0) == find(5)    because 0 and 5 share a subset
find(0) != find(1)    because their subsets differ

After a union, a group’s representative may change. Clients should compare representatives, not store one forever as a permanent group ID unless the API explicitly guarantees stable labels.

Equivalence Classes

Partitions correspond to equivalence relations. Define a ~ b to mean “a and b are in the same subset.” Then the relation is:

• reflexive: a ~ a;
• symmetric: if a ~ b, then b ~ a;
• transitive: if a ~ b and b ~ c, then a ~ c.

Each equivalence class is one subset in the partition.

This viewpoint clarifies what union means. If one fact says a ~ b and another says b ~ c, the structure must place a, b, and c in one class. It cannot keep only the two pairwise links while denying transitivity.

Disjoint-Set ADT

For a fixed universe of integer IDs 0..n-1, the essential operations are:

make_set(x)       create singleton {x}
find(x)           return representative of x's subset
union(a, b)       merge the subsets containing a and b
connected(a, b)   whether find(a) == find(b)

Useful extensions include:

component_size(x)
component_count()

The standard structure supports union but not deletion, splitting, or efficient member enumeration. Those operations require additional or different representations.

Forest Representation

Each element stores a parent index. Roots point to themselves. One rooted tree represents one subset; all trees together form a forest.

parent: [0, 0, 2, 0, 4, 3, 1, 4]

       0              2          4
      / \                        /
     1   3                      7
     |   |
     6   5

The represented partition is:

{0,1,3,5,6}  {2}  {4,7}

Following parent links from any member reaches its root:

find(6): 6 -> 1 -> 0
find(5): 5 -> 3 -> 0

Both return 0, so the elements are connected.

Forest invariant

For n elements:

• every parent[x] is a valid index in [0,n);
• each parent chain terminates at a root r where parent[r] == r;
• parent links contain no directed cycle except each root’s self-link;
• two elements belong to the same subset exactly when their chains reach the same root;
• root-only metadata, such as component size, is authoritative only at roots;
• the number of roots equals the component count.

The particular tree shape is not part of the abstract partition. Parent links may change during a query as long as roots—and therefore membership—remain the same.

Core Operations

Make-set

Creating singleton {x} uses:

parent[x] = x
rank[x] = 0
size[x] = 1

For a fixed universe, initialization performs make-set for every ID in Theta(n) time.

For a dynamic universe, arrays can append another singleton. Growth may relocate storage, but integer IDs remain valid because they are indices rather than pointers.

Find

Without compression, find follows parent links until a root:

size_t find_root(const size_t parent[], size_t x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

Time is proportional to tree height. A careless union policy can produce a chain of height n - 1.

Union

Union must connect roots, not arbitrary original elements:

root_a = find(a)
root_b = find(b)
if root_a != root_b:
    make one root a child of the other

Setting parent[a] = b directly can detach only part of a’s tree or create a cycle when a and b are not roots.

Union of already connected elements changes nothing and must not decrement component count.

Union Trace

Change the merge order in the experiment and compare the resulting parent arrays. Union by size may produce different valid trees while preserving the same partition.

Start with six singleton sets:

parent: [0,1,2,3,4,5]
sets:   {0} {1} {2} {3} {4} {5}

After union(0,1) and union(2,3):

parent: [0,0,2,2,4,5]

  0      2      4    5
  |      |
  1      3

After union(1,3), find reaches roots 0 and 2, then links those roots:

parent: [0,0,0,2,4,5]

       0       4    5
      / \
     1   2
         |
         3

The partition is {0,1,2,3} {4} {5}. The internal parent of 3 can remain 2; it still reaches root 0.

Union Heuristics

Arbitrary root attachment can build tall trees. Union heuristics attach a structurally smaller tree below a larger one.

Union by size

Each root stores the number of members in its component. Attach the smaller component’s root below the larger:

if (set_size[root_a] < set_size[root_b]) {
    size_t temporary = root_a;
    root_a = root_b;
    root_b = temporary;
}
parent[root_b] = root_a;
set_size[root_a] += set_size[root_b];

When a node’s depth increases by one, its new component is at least twice the size of its former component. No element can have its depth increased more than floor(log2 n) times, so height is O(log n) even without path compression.

Only root sizes are authoritative. The old child root’s size field may remain stale or be cleared; clients must query the current root.

Union by rank

Rank is an upper-bound measure of tree height. Attach lower rank below higher rank. If ranks are equal, choose either root and increase the winner’s rank by one.

if (rank[root_a] < rank[root_b]) {
    parent[root_a] = root_b;
} else if (rank[root_a] > rank[root_b]) {
    parent[root_b] = root_a;
} else {
    parent[root_b] = root_a;
    ++rank[root_a];
}

After path compression, rank is no longer the exact current height. It remains a valid ordering heuristic and should not be recomputed as height.

Use size or rank; neither must be combined with the other to obtain the classical bound. Size is useful when component-size queries are needed. Rank can be stored in very few bits.

Path Compression

Path compression makes every node visited by find point directly to the root.

Before find(7):

7 -> 6 -> 4 -> 2 -> 0

After:

7 ─┐
6 ─┤
4 ─┼─> 0
2 ─┘

The partition has not changed. Only redundant internal routes have shortened.

Recursive compression

size_t find_compress(size_t parent[], size_t x) {
    if (parent[x] != x) {
        parent[x] = find_compress(parent, parent[x]);
    }
    return parent[x];
}

The assignment occurs while recursive calls return, rewriting each visited link to the root. A very deep unoptimized forest can exhaust the call stack before its first compression, so an iterative implementation is safer for untrusted state.

Iterative compression

Use two passes: first find the root, then rewrite the path.

size_t root = x;
while (parent[root] != root) {
    root = parent[root];
}
while (parent[x] != x) {
    size_t next = parent[x];
    parent[x] = root;
    x = next;
}

Path halving

Path halving points each visited node to its grandparent during one upward walk:

while (parent[x] != x) {
    parent[x] = parent[parent[x]];
    x = parent[x];
}

It may not flatten the entire path in one call, but repeated operations become extremely fast. Full compression, splitting, and halving share the same goal with different write patterns.

Union-Find Program

This complete C17 structure uses union by rank, full iterative path compression, root component sizes, and a component counter.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    size_t *parent;
    unsigned *rank;
    size_t *set_size;
    size_t count;
    size_t components;
} DisjointSets;

static bool dsu_indices_valid(const DisjointSets *sets) {
    if (sets == NULL) {
        return false;
    }
    for (size_t i = 0; i < sets->count; ++i) {
        if (sets->parent[i] >= sets->count) {
            return false;
        }
    }
    return true;
}

void dsu_destroy(DisjointSets *sets) {
    free(sets->parent);
    free(sets->rank);
    free(sets->set_size);
    sets->parent = NULL;
    sets->rank = NULL;
    sets->set_size = NULL;
    sets->count = 0;
    sets->components = 0;
}

bool dsu_init(DisjointSets *sets, size_t count) {
    sets->parent = NULL;
    sets->rank = NULL;
    sets->set_size = NULL;
    sets->count = 0;
    sets->components = 0;

    if (count == 0) {
        return true;
    }
    if (count > SIZE_MAX / sizeof *sets->parent ||
        count > SIZE_MAX / sizeof *sets->rank ||
        count > SIZE_MAX / sizeof *sets->set_size) {
        return false;
    }

    sets->parent = malloc(count * sizeof *sets->parent);
    sets->rank = calloc(count, sizeof *sets->rank);
    sets->set_size = malloc(count * sizeof *sets->set_size);
    if (sets->parent == NULL || sets->rank == NULL ||
        sets->set_size == NULL) {
        dsu_destroy(sets);
        return false;
    }

    sets->count = count;
    sets->components = count;
    for (size_t i = 0; i < count; ++i) {
        sets->parent[i] = i;
        sets->set_size[i] = 1;
    }
    assert(dsu_indices_valid(sets));
    return true;
}

bool dsu_find(DisjointSets *sets, size_t element, size_t *root_out) {
    assert(dsu_indices_valid(sets));
    if (element >= sets->count || root_out == NULL) {
        return false;
    }

    size_t root = element;
    while (sets->parent[root] != root) {
        root = sets->parent[root];
    }

    size_t current = element;
    while (sets->parent[current] != current) {
        size_t next = sets->parent[current];
        sets->parent[current] = root;
        current = next;
    }

    *root_out = root;
    assert(dsu_indices_valid(sets));
    return true;
}

bool dsu_union(DisjointSets *sets, size_t a, size_t b, bool *merged) {
    if (merged == NULL) {
        return false;
    }

    size_t root_a;
    size_t root_b;
    if (!dsu_find(sets, a, &root_a) ||
        !dsu_find(sets, b, &root_b)) {
        return false;
    }
    if (root_a == root_b) {
        *merged = false;
        return true;
    }

    if (sets->rank[root_a] < sets->rank[root_b]) {
        size_t temporary = root_a;
        root_a = root_b;
        root_b = temporary;
    }

    sets->parent[root_b] = root_a;
    sets->set_size[root_a] += sets->set_size[root_b];
    if (sets->rank[root_a] == sets->rank[root_b]) {
        ++sets->rank[root_a];
    }
    --sets->components;
    *merged = true;
    assert(dsu_indices_valid(sets));
    return true;
}

bool dsu_connected(DisjointSets *sets, size_t a, size_t b,
                   bool *connected) {
    if (connected == NULL) {
        return false;
    }
    size_t root_a;
    size_t root_b;
    if (!dsu_find(sets, a, &root_a) ||
        !dsu_find(sets, b, &root_b)) {
        return false;
    }
    *connected = root_a == root_b;
    return true;
}

bool dsu_component_size(DisjointSets *sets, size_t element,
                        size_t *size_out) {
    if (size_out == NULL) {
        return false;
    }
    size_t root;
    if (!dsu_find(sets, element, &root)) {
        return false;
    }
    *size_out = sets->set_size[root];
    return true;
}

int main(void) {
    DisjointSets sets;
    if (!dsu_init(&sets, 8)) {
        return EXIT_FAILURE;
    }

    size_t pairs[][2] = {{0,3}, {3,5}, {1,6}, {4,7}, {5,6}};
    for (size_t i = 0; i < sizeof pairs / sizeof pairs[0]; ++i) {
        bool merged;
        if (!dsu_union(&sets, pairs[i][0], pairs[i][1], &merged)) {
            dsu_destroy(&sets);
            return EXIT_FAILURE;
        }
    }

    bool connected;
    size_t component_size;
    dsu_connected(&sets, 0, 1, &connected);
    dsu_component_size(&sets, 0, &component_size);
    printf("0 and 1: %s\n", connected ? "connected" : "separate");
    printf("component size: %zu\n", component_size);
    printf("components: %zu\n", sets.components);

    dsu_destroy(&sets);
    return EXIT_SUCCESS;
}

The implementation stores sizes even though rank chooses the new root. After attaching root_b, only set_size[root_a] is authoritative. Component-size queries always perform find before reading metadata.

The lightweight validator checks index safety but not acyclicity. A full debug validator can color parent walks, count roots, sum root sizes, and ensure every walk terminates; doing so costs linear time or more and is not appropriate inside every production operation.

Component Queries

Connectivity

Two valid elements are connected exactly when their representatives match:

connected(a, b) = find(a) == find(b)

Find may compress both paths, so a logically read-only query mutates representation for future speed. In C APIs this means connected cannot take a pointer to const when it performs compression.

Component size

Store size at roots and update it during union. Querying set_size[element] directly is wrong when element is not a root.

Component count

Initialize to n. Decrement exactly when union merges two distinct roots. This answers “how many groups remain?” in constant time.

Enumerating members

The basic forest does not maintain child collections or member lists. To enumerate one component, scan all n elements and compare roots, costing near Theta(n).

Maintaining linked member lists can make enumeration proportional to component size, but union must splice lists and the structure carries more metadata. Representation should follow whether enumeration is a core operation.

Connectivity Tracking

Suppose a network begins with isolated devices. Each new physical link calls union(u,v). At any time:

• connected(u,v) answers whether transitive links join them;
• components counts isolated network regions;
• component size measures the region containing a device.

The structure remembers connectivity, not actual edges or routes. It cannot list a path between two devices because union discards which edge sequence established the connection. Pair it with a graph when path reconstruction is required.

Offline connectivity

If edges only arrive, union-find answers connectivity online. If edges are deleted, ordinary union-find cannot split components. Some deletion problems can be processed offline by reversing time and turning deletions into additions; fully dynamic connectivity needs structures designed to support deletion.

Cycle Detection

For an undirected graph processed edge by edge:

• if endpoints are in different components, union them;
• if endpoints are already connected, the new edge closes a cycle.

bool add_forest_edge(DisjointSets *sets, size_t u, size_t v,
                     bool *creates_cycle) {
    if (creates_cycle == NULL) {
        return false;
    }
    bool connected;
    if (!dsu_connected(sets, u, v, &connected)) {
        return false;
    }
    if (connected) {
        *creates_cycle = true;
        return true;
    }
    bool merged;
    if (!dsu_union(sets, u, v, &merged)) {
        return false;
    }
    *creates_cycle = false;
    return true;
}

This criterion does not directly detect directed cycles; reachability direction matters there. Self-loops and parallel undirected edges also require the graph model’s definitions: a self-loop creates a cycle immediately, and a second parallel edge forms a length-two cycle in a multigraph convention.

Cycle detection is an application of the data structure. Full graph-algorithm treatment remains in Algorithms.

Algorithm Bridges

Kruskal’s minimum-spanning-tree algorithm considers edges by increasing weight and uses union-find to reject edges whose endpoints are already connected. The heap or sorting method orders candidates; disjoint sets answer whether accepting one would join two components.

Other uses include image region labeling, network account merging, percolation simulation, equivalence constraints, and clustering. In each case, relationships accumulate monotonically and the main question is component membership.

Amortized Costs

No heuristics

Arbitrary union can form a chain, making find Theta(n).

One union heuristic

Union by size or rank alone keeps height O(log n), so find and union are O(log n) worst case.

Compression alone

Path compression speeds repeated finds, but combining it with a union heuristic gives the standard strongest bound and avoids deliberately poor initial shapes.

Combined bound

For a sequence of m make-set, union, and find operations on n elements, union by rank or size plus path compression takes:

O((m + n) alpha(n))

where alpha is the inverse Ackermann function under a standard formulation. For every practical input size, alpha(n) is at most a tiny constant. The structure is therefore often described as “almost constant amortized time.”

This is not literal worst-case constant time for each individual operation. A find may traverse several links before compressing them. The bound averages total cost across the operation sequence.

Inverse-Ackermann Bound

The Ackermann function grows faster than ordinary exponentials, towers, and most functions encountered in programs. Its inverse asks roughly how many times an extremely fast-growing hierarchy must be stepped down before reaching a small value.

Because the forward function grows so quickly, the inverse grows extraordinarily slowly. The exact definition varies with the analysis convention, but that does not change the engineering conclusion: rank plus path compression makes forest navigation effectively constant for realistic sizes while retaining a rigorous near-constant amortized guarantee.

Do not replace alpha(n) with log n in theoretical statements; the inverse-Ackermann result is substantially stronger. Also do not claim every call is constant time; the result concerns sequences.

Forest Storage

The array representation uses:

• one parent index per element;
• one rank or size value per element, although only roots need current root metadata;
• optional component size and application payload.

Total storage is Theta(n). Dense arrays have excellent locality and no per-node allocator overhead. Arbitrary external keys can be mapped to dense IDs through a hash table.

Choosing Partitions

Explicit labels

An array assigning each element a component label makes find constant time. Merging two labels requires scanning and relabeling many elements, potentially Theta(n) per union.

Member lists

Maintaining one list per component can support enumeration and weighted relabeling. It uses more links and still needs a mapping from each element to its component.

Edge-preserving graphs

A graph retains edges and can reconstruct paths or handle directional relationships. Union-find retains only partition membership and is much smaller for monotonic connectivity queries.

Hash sets

A hash set answers whether an individual key exists. Disjoint sets answer whether two known elements share an equivalence class. Their use of the word “set” describes different operations.

Representative Labels

The forest root is a structural representative, not necessarily the label a user wants to see. Union by rank is free to choose either equal-rank root, and a later union may make today’s root a child:

before: component {2,5} has root 2
union with larger component rooted at 9
after:  find(2) == 9

Returning 9 as a permanent group identity would therefore be unsafe. Separate three ideas:

• element ID: stable identity of an individual element;
• root: current internal representative used by the forest;
• component label: optional application-facing name for the group.

If the desired label is the smallest element in each component, store minimum[root] as root metadata. During a successful union:

minimum[new_root] = min(minimum[root_a], minimum[root_b])

The forest can still choose roots by rank or size; label policy does not control tree shape. component_label(x) first finds the current root and then reads its minimum.

For a label that must remain stable across merges, the application needs a merge rule. It might preserve the older component’s UUID, choose one label deterministically, or create a new label and record aliases from both former labels. No data structure can make two distinct old group identities remain the one unique identity of their merged group without defining such semantics.

Never use a cached root as a later array index for root-only metadata. Store the element ID and call find again, or expose an opaque component handle backed by a separate label layer.

Compression Trace

Path compression is easiest to understand by separating discovery from rewriting. Begin with:

index:  0 1 2 3 4 5 6 7
parent: 0 0 1 2 3 4 5 6

7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0

The first pass uses a temporary root and makes no writes:

root=7,6,5,4,3,2,1,0

Only after reaching self-parent 0 does the second pass rewrite. Saving next before overwriting is essential:

x=7: next=6, parent[7]=0
x=6: next=5, parent[6]=0
x=5: next=4, parent[5]=0
x=4: next=3, parent[4]=0
x=3: next=2, parent[3]=0
x=2: next=1, parent[2]=0
x=1: next=0, parent[1]=0
x=0: stop

The final array is:

[0,0,0,0,0,0,0,0]

If the loop assigned parent[x] = root and then tried x = parent[x], it would jump directly to the root after one write and leave the rest of the path uncompressed. Connectivity would still be correct, so a shallow functional test might miss the lost optimization.

Compression writes links only toward the already established root. It does not alter rank. Rank summarizes historical merging and remains an upper bound used for future root choice; it is not recalculated from the now-flatter physical tree.

Find is often called a query, but compressing find mutates parent. A truly read-only find_const can follow links without rewriting. That can be useful during concurrent reads, debugging, or access through a const DisjointSets *, although it gives up the future speed improvement of that query.

Metadata Bounds

Union by rank works because rank growth certifies component growth. A root begins at rank 0 and represents at least one element, which is 2^0. Rank increases from r to r + 1 only when two rank-r roots merge. Each represents at least 2^r elements, so the merged component contains at least:

2^r + 2^r = 2^(r + 1)

By induction, a root of rank r represents at least 2^r elements. Therefore r <= floor(log2 n). This explains why rank needs few bits: even a component with billions of elements has a rank around only a few dozen.

Union by size has a related per-element argument. Whenever an element’s depth increases, its former component was attached below a component at least as large, so its new component size at least doubles. An element can experience at most floor(log2 n) such depth increases.

The metadata invariants differ:

size[root] = exact number of represented elements
rank[root] = historical upper-bound measure used for attachment

Size changes on every successful union. Rank changes only on an equal-rank union. Compression changes neither. A validator can recompute exact sizes but should not demand that rank equal current height after compression.

If both fields are stored, decide which selects the parent. Updating size correctly does not rescue incorrect rank selection, and maintaining unused metadata adds opportunities for bugs. Store size when clients query it; store rank when compact heuristic metadata is preferred.

Dynamic Elements

Array-based union-find naturally uses dense IDs. To add a new element, append corresponding entries to every metadata array:

new ID x = old count
parent[x] = x
rank[x] = 0
set_size[x] = 1
count++
components++

Growing three separate allocations creates a transaction problem. If parent growth succeeds but rank growth fails, publishing only the new parent pointer produces mismatched capacities. Safe designs include:

• allocate complete replacement arrays, copy all old fields, initialize the new slot, then commit all pointers together;
• store per-element metadata in one dynamic array of structures, so one successful reallocation grows every field together;
• keep separate arrays but track and grow their capacities independently without exposing the new element until every required array has room.

An array of structures is often the simplest:

typedef struct {
    size_t parent;
    size_t set_size;
    unsigned rank;
} DsuNode;

Relocating this array does not invalidate integer IDs. It does invalidate pointers into the array, so public APIs should accept IDs rather than expose DsuNode * handles.

Arbitrary external keys require a dictionary from key to dense ID. Adding key "device-17" first reserves a DSU ID and inserts the mapping. Failure ordering matters: do not leave a dictionary entry pointing at an uninitialized DSU slot, and do not make an unreachable DSU element if dictionary insertion fails. Prepare both resources, then publish them together or define cleanup that rolls back the uncommitted side.

Removing an individual element is not an ordinary inverse operation. Other nodes may point through it, component sizes would change, and deleting it may split one component into several. A dynamic universe can support append while still explicitly rejecting remove.

Forest Audits

Checking only parent[x] < count prevents an out-of-bounds read but does not prove that chains terminate. A full debug audit can classify every node with three colors:

white: unvisited
gray:  currently on this parent walk
black: already proved to reach a valid root

For each white element, follow parents. Encountering an invalid index is corruption. Encountering a gray node is a cycle unless that node points to itself as the terminating root. Encountering a black node joins an already validated route. Mark the completed path black.

After validating termination:

1. count indices where parent[x] == x and compare with components;
2. find the root of every element without modifying the structure;
3. accumulate a temporary count per root;
4. compare each root count with set_size[root];
5. if labels such as minimum are stored, recompute and compare them;
6. check that rank strictly increases along parent edges when union-by-rank invariants promise it.

Rank need not increase by exactly one on an edge, and non-root rank values need not describe current subtree height. The audit should validate only promised facts.

For small randomized tests, an explicit-label oracle is even simpler. find(x) returns label[x]; union scans the full label array and replaces one label with the other. Its merge is slow Theta(n) but its state is easy to inspect. After every generated union or query, compare connectivity for all pairs and component sizes for all elements.

Generate redundant unions, reversed argument orders, singleton queries, long precompression paths, and invalid IDs. Save the operation sequence and parent array for any failure. An invariant failure immediately after one operation is far easier to diagnose than an incorrect final component count.

Rollback Forests

Some applications need snapshots and undo rather than the fastest possible ordinary find. A rollback variant records each union’s changed fields on a history stack:

changed child root
its previous parent
winning root
its previous size or rank
previous component count

A snapshot is the current history length. Rolling back pops and reverses records until that length is restored. Redundant unions also need a marker so one rollback corresponds to one attempted update when the API promises that behavior.

Full path compression conflicts with cheap rollback because one find may rewrite many parent links, all of which would need history records. Rollback union-find therefore commonly uses union by size or rank without compression, retaining O(log n) find height and O(1) recorded changes per successful union.

This is not a feature to bolt invisibly onto the standard structure. It is a different representation contract: queries no longer compress, node metadata changes are logged, and old snapshots become invalid if history is discarded. Choose it only when version reversal is a core operation.

Persistent variants that allow querying several historical versions require further structural sharing or versioned arrays. Ordinary union-find is optimized for one current, monotonically merged partition.

Concurrent Access

Compression means two threads performing only connected queries may both write the parent array. Without synchronization, that is a data race in C even if both intend to write the same root. Union also updates parent, rank or size, and component count as one logical mutation.

Simple safe choices are:

• guard every operation with one mutex;
• permit concurrent find_const calls while excluding union and compressing find;
• partition work into thread-local forests and merge results under controlled coordination.

Fine-grained lock-free union-find exists, but it needs atomic operations and a proof that parent updates, root choice, and metadata remain coherent. Ordinary educational code should not be described as thread-safe merely because parent assignments look idempotent.

Union-Find Hazards

Unioning non-roots

Setting parent[a] = b without first finding both roots can detach a subtree, build avoidable depth, or create a parent cycle.

Stale representatives

A root returned before union may become a child afterward. Compare fresh find results rather than treating representatives as stable public IDs.

Reading non-root metadata

Size and rank are meaningful according to their root-only contracts. Always locate the root before querying component size.

Incorrect rank updates

Increase rank only when two equal-rank roots merge. Increasing it on every union destroys the reasoning behind the heuristic.

Recursive stack depth

Recursive find is concise but can encounter a long pre-compression chain. Iteration avoids runtime stack exhaustion.

Invalid element IDs

An out-of-range parent access is memory corruption. Validate IDs at public boundaries before following parent links.

Assuming deletions

Removing an edge from the original problem does not undo a union. The forest has discarded the internal evidence needed to split safely.

Directed misuse

Undirected connectivity equivalence is symmetric. Directed reachability is not, so it cannot be represented as ordinary disjoint-set equivalence classes.

Forest Validation

Test partition semantics and structural shortcuts separately:

1. zero elements and one singleton;
2. union of two singletons;
3. union of already connected elements;
4. unions where lower rank appears as either argument;
5. equal-rank merge and rank increment;
6. component sizes after several merge orders;
7. component count after successful and redundant unions;
8. a deliberately deep valid forest followed by compression;
9. invalid element IDs;
10. cycle detection with trees, one closing edge, loops, and parallel edges.

For randomized tests, maintain an elementary component-label array as a slow reference. After each union, compare connectivity for every element pair and verify the sum of root component sizes is n.

Union-Find Essentials

• Disjoint sets maintain a partition into equivalence classes under monotonic union.
• Parent-pointer trees represent each subset; roots serve as current representatives.
• Union must connect roots, and find follows parent links to a root.
• Union by size or rank prevents tall trees.
• Path compression shortens query paths without changing the represented partition.
• Component size and rank are root metadata; representative identity may change.
• Dense arrays provide linear storage and strong locality.
• Rank or size plus path compression gives near-constant amortized operations bounded by inverse-Ackermann growth.
• The structure tracks connectivity but discards paths, edges, direction, and the ability to split components.

Union-Find Problems

Partition Rules

1. State the partition and forest invariants.
2. Explain why representatives are not necessarily stable group IDs.
3. Distinguish union by size from union by rank.
4. Why can a logically read-only connectivity query modify parent links?

Forest Traces

5. Starting from eight singletons, trace union(0,1), union(2,3), union(4,5), union(6,7), union(1,3), union(5,7), and union(3,7) by rank.
6. Record parent, rank, size, and component count after every operation.
7. Perform find on every element and show the fully compressed forest.
8. Process an undirected edge list and identify the first cycle-closing edge.

Union Failures

9. Construct a cycle caused by assigning parent[a] = b without locating roots.
10. Find the component-count bug in code that decrements after every union call.
11. Explain why reading set_size[x] without find can return stale data.
12. Diagnose rank code that increments the winning rank after unequal-rank union.

Forest Variants

13. Replace union by rank with union by size in the reference implementation.
14. Implement path halving and compare parent arrays after repeated finds.
15. Add dynamic make-set while preserving existing integer IDs on allocation failure.
16. Write a full validator that detects invalid parent indices, non-root cycles, wrong component count, and wrong root sizes.
17. Map string keys to dense IDs and expose a key-based union-find API.

Partition Choices

18. Add member enumeration and state the new union and storage costs.
19. Decide whether union-find can represent users who may leave groups, and propose a more suitable approach if not.
20. Design stable external component labels even though structural roots may change.
21. Compare a graph plus traversal with disjoint sets for one million incremental connectivity queries.

Rollback and Bounds

22. Prove the logarithmic-height bound for union by size without compression.
23. Process edge deletions offline by reversing time and turning them into insertions.
24. Implement rollback union-find without path compression and explain why ordinary compression conflicts with efficient rollback.