Parent forests and finding a root

After this page, you should be able to:

• Follow parent links to roots and state the parent-forest invariant.

• Explain why root linking preserves groups but arbitrary reparenting may not.

Builds on: Partitions and representatives and array/reference models.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

JavaScript member indices are 0..n−1; Julia members are 1..n. Element count, component count and component size remain distinct. Julia find_set! and union_sets! may mutate representation links, preserving the same abstract partition and union-by-size tie rule.

Represent each set as a rooted tree¶

Store one parent index per member. A root points to itself: parent[root] == root. Other members follow parent links until they reach that root. Different root trees represent different disjoint sets, forming a forest.

For [0, 0, 0, 2, 4, 4, 6], the represented groups are {0,1,2,3}, {4,5} and {6}. Member 3’s immediate parent is 2, but its representative is 0.

Follow the entire path, not just one parent¶

def find_root(parent, x):
    while parent[x] != x:
        x = parent[x]
    return x

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

function find_root(parent, x)
    while parent[x] != x; x = parent[x]; end
    return x
end

The helper assumes a valid index and a well-formed parent forest. find_root(parent, 3) follows 3, 2, 0 and returns 0. find_root(parent, 1) follows 1, 0 and returns the same representative. Testing only parent[3] == parent[1] would incorrectly claim they belong to different sets.

Merge roots rather than arbitrary interior nodes¶

To combine two sets, first find their distinct roots, then make one root point to the other. Redirecting an arbitrary member can detach only part of a component or create a cycle in the representation. Root linking preserves all existing members and keeps one tree per abstract set.

Unrestricted root linking can still produce a chain, making one find take $\Theta(n)$ time. The next page controls that depth and shortens paths.

Parent links are bookkeeping, not original graph routes¶

Union may connect two root indices even when no original graph edge joins those roots. Path compression later adds further shortcuts that were never input edges. The parent forest therefore cannot be interpreted as a route network or as Kruskal’s chosen spanning edges.

Keep accepted graph edges in a separate list if they are needed. This distinction also prevents confusing a graph traversal’s discovery parent—which denotes an actual graph edge—with a union–find parent.

Helper contract, costs and alternatives¶

find_root(parent, x) observes a supplied well-formed parent array and returns a root. It does not compress, check indices or maintain component sizes/counts. Invalid arrays can loop forever or raise errors; Python’s negative indices are not an intended membership policy. The public DisjointSet class adds explicit checks.

For a path with h parent links, this iterative helper uses Θ(h+1) time and O(1) auxiliary space. A plain forest uses Θ(n+1) persistent storage and may have h=n−1. Root linking after roots are known costs O(1); finding those roots is additional work. Union by size controls height, while compression repairs paths during find. Neither operation needs to sort member labels or preserve input graph edges.

Check your understanding¶

Predict the result or state change before opening the explanation.

1. For parent = [0,0,0,2,4,4,6], are 1 and 3 connected despite having parents 0 and 2?

2. Can a compressed parent link be used as a road in a recovered graph route?

Next: Union by size and compression.