UnionFind
Attributes
- Experimental
- true
- Graph
-
- Supertypes
-
class Objecttrait Matchableclass Any
Members list
Value members
Concrete methods
Path-compressing: every node on the way to the root is repointed directly at it, so repeated find calls into the same subtree are O(1) after the first.
Path-compressing: every node on the way to the root is repointed directly at it, so repeated find calls into the same subtree are O(1) after the first.
Attributes
Union by rank, root-to-root: the shallower tree's root is repointed at the deeper one's, keeping both bounded at O(log n) depth. Does not preserve the original edge (x, y) as a parent link -- pathsFrom/cycleToChain below reconstruct tree paths from lrList._1 directly, not from these pointers.
Union by rank, root-to-root: the shallower tree's root is repointed at the deeper one's, keeping both bounded at O(log n) depth. Does not preserve the original edge (x, y) as a parent link -- pathsFrom/cycleToChain below reconstruct tree paths from lrList._1 directly, not from these pointers.