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.