How do I implement a disjoint set (union-find) in Go?

A disjoint set (also known as union-find) is a data structure that keeps track of elements partitioned into disjoint subsets. It provides efficient operations to find the set a particular element belongs to and to unite two sets. Below is a simple implementation of a disjoint set in Go.

Go, Disjoint Set, Union-Find, Data Structure, Go Implementation

This example demonstrates a simple and efficient union-find implementation in Go. It includes both union and find operations with path compression for optimization.

package main import "fmt" type DisjointSet struct { parent []int rank []int } func NewDisjointSet(size int) *DisjointSet { parent := make([]int, size) rank := make([]int, size) for i := range parent { parent[i] = i rank[i] = 0 } return &DisjointSet{parent: parent, rank: rank} } func (ds *DisjointSet) Find(i int) int { if ds.parent[i] != i { ds.parent[i] = ds.Find(ds.parent[i]) // Path compression } return ds.parent[i] } func (ds *DisjointSet) Union(i int, j int) { rootI := ds.Find(i) rootJ := ds.Find(j) if rootI != rootJ { if ds.rank[rootI] > ds.rank[rootJ] { ds.parent[rootJ] = rootI } else if ds.rank[rootI] < ds.rank[rootJ] { ds.parent[rootI] = rootJ } else { ds.parent[rootJ] = rootI ds.rank[rootI]++ } } } func main() { ds := NewDisjointSet(10) ds.Union(1, 2) ds.Union(2, 3) ds.Union(4, 5) fmt.Println(ds.Find(1)) // Output: root of 1 fmt.Println(ds.Find(2)) // Output: root of 1 fmt.Println(ds.Find(3)) // Output: root of 1 fmt.Println(ds.Find(4)) // Output: root of 4 }

Go Disjoint Set Union-Find Data Structure Go Implementation

Related Questions

How do I avoid rehashing overhead with std::set in multithreaded code?

How do I find elements with custom comparators with std::set for embedded targets?

How do I erase elements while iterating with std::set for embedded targets?

How do I provide stable iteration order with std::unordered_map for large datasets?

How do I reserve capacity ahead of time with std::unordered_map for large datasets?

How do I erase elements while iterating with std::unordered_map in multithreaded code?

How do I provide stable iteration order with std::map for embedded targets?

How do I provide stable iteration order with std::map in multithreaded code?

How do I avoid rehashing overhead with std::map in performance-sensitive code?

How do I merge two containers efficiently with std::map for embedded targets?