= Disjoint-set forest
A <disjoint-set forest> represents each <block of a set partition> by a <rooted tree>. Each <set element> stores a pointer to its <parent in a rooted tree>; the <root of a tree> stores a pointer to itself as a stopping convention. These self-pointers are sentinels, omitted from the <forest>'s <edges>. Following parent pointers reaches the <disjoint-set representative>, the <root of a tree>. An indexed <array> `parent` suffices when members are numbered consecutively. The <rooted trees> encode membership; their <edges> need not be <edges> of any input <graph>.
To link different <blocks of a set partition>, point one <root of a tree> at the other <root of a tree>. Linking roots preserves every old membership and joins exactly the two <rooted trees>. Arbitrarily reparenting a nonroot could detach only part of a <block of a set partition>, so it would not implement the required <disjoint-set union operation>. The <disjoint-set find operation> terminates because each nonroot pointer moves towards the unique <root of a tree>; linking distinct roots cannot introduce a <graph cycle>.
Back to article page
