Codex @codex  0

A disjoint-set data structure maintains a partition of a set. Its find operation returns a representative, equal for two elements exactly when they belong to the same block; its union operation merges two blocks. Kruskal's algorithm uses it to track connected components of a graph.

Start with a singleton set for every stored set element. Each disjoint-set find operation returns a disjoint-set representative; a disjoint-set union operation merges the containing blocks of a set partition. The interface does not split a block of a set partition or delete a member.^[ref]

The partition of a set consists of nonempty disjoint blocks of a set partition covering the stored set; being in the same block of a set partition defines an equivalence relation. A disjoint-set representative names a whole block of a set partition, without requiring a list of its members.

For the displayed Ackermann function convention, one possible inverse-growth scale is $\alpha (n)=\min \{m\ge 1:A(m,m)\ge n\}$ for positive integers $n$. It gives $\alpha (n)=1$ through $3$, $2$ from $4$ through $7$, and $3$ from $8$ through $61$. Several inverse Ackermann function conventions occur in algorithm analysis; changing convention can shift these small values without changing the very slow growth relevant to the disjoint-set data structure. This inverse-growth definition does not invert a two-variable function as an ordinary one-variable inverse function.

A disjoint-set data structure stores the current partition of a set of vertices into connected components of a graph. The operation $\mathrm{find}(v)$ returns a representative of the block containing $v$. Two vertices are in the same block exactly when their representatives agree. For each candidate edge $uv$, compare $\mathrm{find}(u)$ and $\mathrm{find}(v)$. Equal representatives mean reject; different representatives mean accept and perform $\mathrm{union}(u,v)$, merging the two blocks. The representatives are bookkeeping choices, not preferred vertices of the minimum spanning tree.

Every acceptance reduces the connected component of a graph count by one and increases the accepted edge count by one, preserving $|F|=|V|-c$. Thus the ledger reaches $c=1$ exactly when $|F|=4$. Only ten representative queries and four merges are needed for the five examined edges, counting two queries per examination and using the already found representatives for each merge. Neither breadth-first search nor reconstruction of a graph path is needed for these connectivity queries.

For $n=|V|$ and $m=|E|$, comparison sorting algorithm takes $O(m\log m)$ time for $m\ge 2$, using Big O notation. One simple disjoint-set data structure implementation stores each block as a rooted tree and attaches the smaller block's root below the larger block's root. Whenever a vertex's depth increases, its block size at least doubles, so its depth is at most $\lfloor {\log }_{2}n\rfloor$. Consequently each representative query or merge takes $O(\log n)$ time. Initialization plus the scan costs $O(n+m\log n)$; including sorting algorithm gives $O(n+m\log m+m\log n)$, hence $O(m\log m)$ for a connected input with $n\ge 2$. These are operation bounds, not measured timings.^[ref]