dsu

Disjoint Set Union (Union Find) performance focused 🔥 implementation in Golang.

func ExampleDsu() {
    d := dsu.NewDsu(3)
    d.Union(0, 1)

    if d.Find(0) == d.Find(1) {
        fmt.Println("0 and 1 are in the same set")
    }

    if d.Find(1) != d.Find(2) {
        fmt.Println("1 and 2 are in different sets")
    }

    if d.Size(0) == 2 {
        fmt.Println("Set with the element 0 has 2 elements")
    }

    // Output:
    // 0 and 1 are in the same set
    // 1 and 2 are in different sets
    // Set with the element 0 has 2 elements
}

My benchmarks show a <50ns/op performance for random (non-empty) union operations.

$ go test -bench .
goos: darwin
goarch: arm64
pkg: alon.kr/x/dsu
cpu: Apple M2 Pro
BenchmarkRandomUnions-10        44521050                48.64 ns/op
PASS
ok      alon.kr/x/dsu   6.390s