const MaxN
MaxN bounds a set so allocation stays predictable.
v0 source pure
Package disjointset is union-find (a disjoint-set forest) as a pure, reusable package: it tracks a partition of \[0, ...
View source
gno.land/p/moul/x/daily/disjointset/v0
Union-find (disjoint-set forest) — New, Find, Union, Connected,
Size, Groups, Partition, MaxN.
Tracks a partition of [0, n) into disjoint groups and answers "same group?" in
near-constant time.
1import "gno.land/p/moul/x/daily/disjointset/v0"
2
3d := disjointset.New(10)
4d.Union(0, 1)
5d.Union(1, 3)
6d.Connected(0, 3) // true
7d.Groups() // 8
8d.Partition() // [[0 1 3] [2] [4] ...]
Both optimisations, because they only work together: path compression
flattens the tree on every Find, union by rank keeps the shallower tree under
the deeper one. With both, operations are O(α(n)) — inverse Ackermann,
effectively constant. With neither, a chain of unions degrades to O(n) per
query, which on chain is the difference between a cheap call and running out of
gas. Find compresses iteratively: a deep chain would otherwise risk the
call stack.
Partition returns groups sorted ascending and ordered by their smallest
member, so the result is identical regardless of the order unions were
applied — that determinism is what makes it safe to put in a Render.
Out-of-range indices return -1/false/0 rather than panicking, and are
connected to nothing — not even to themselves.
Live demo: r/moul/x/daily/disjointsetdemo
· render it at /r/moul/x/daily/disjointsetdemo/v0.
Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.
🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.
Package disjointset is union-find (a disjoint-set forest) as a pure, reusable package: it tracks a partition of [0, n) into disjoint groups and answers "are these two in the same group?" in near-constant time.
Both classic optimisations are implemented, and they matter together: path compression flattens a tree on every Find, union by rank keeps the shallower tree under the deeper one. With both, operations are O(α(n)) — inverse Ackermann, effectively constant. With neither, a chain of unions degrades to O(n) per query, which on chain is the difference between a cheap call and an out-of-gas one.
A live demo of this package is at r/moul/x/daily/disjointsetdemo(/r/moul/x/daily/disjointsetdemo/v0).
1
1
1
type DisjointSet
structDisjointSet is a partition of [0, n) into disjoint groups.
Methods on DisjointSet
func Connected
method on DisjointSetConnected reports whether a and b are in the same group. Out-of-range indices are not connected to anything, including themselves.
func Find
method on DisjointSetFind returns the representative of i's group, or -1 when i is out of range.
Path compression: every node visited is re-pointed straight at the root, so the next Find on any of them is O(1). Done iteratively rather than recursively — a deep chain would otherwise risk the call stack.
func Groups
method on DisjointSetGroups returns how many disjoint groups remain.
func InRange
method on DisjointSetInRange reports whether i is a valid element.
func Len
method on DisjointSetLen returns the number of elements.
func Partition
method on DisjointSetPartition returns the groups, each sorted ascending, ordered by their smallest member — deterministic regardless of the union order, which is what makes it safe to render.
func Size
method on DisjointSetSize returns how many elements share i's group, or 0 when out of range.
func Union
method on DisjointSetUnion merges the groups of a and b and reports whether they were merged. False means they were already together, or an index was out of range.