Go语言中如何优雅地泛化不相交集（DisjointSets）数据结构

package main

import "fmt"

// DisjointSets 结构体定义，目前仅支持 int64 类型
type DisjointSets struct {
    ranks map[int64]int64
    p map[int64]int64
}

// NewDisjointSets 创建并返回一个新的 DisjointSets 实例
func NewDisjointSets() *DisjointSets {
    d := DisjointSets{map[int64]int64{}, map[int64]int64{}}
    return &d
}

// MakeSet 将元素 x 添加到不相交集中，作为其自身集合的代表
func (d *DisjointSets) MakeSet(x int64) {
    d.p[x] = x
    d.ranks[x] = 0
}

// Link 根据秩（rank）合并两个根节点 x 和 y
func (d *DisjointSets) Link(x, y int64) {
    if d.ranks[x] > d.ranks[y] {
        d.p[y] = x
    } else {
        d.p[x] = y
        if d.ranks[x] == d.ranks[y] {
            d.ranks[y] += 1
        }
    }
}

// FindSet 查找元素 x 所属集合的代表元素，并进行路径压缩
func (d *DisjointSets) FindSet(x int64) int64 {
    if x != d.p[x] {
        d.p[x] = d.FindSet(d.p[x]) // 路径压缩
    }
    return d.p[x]
}

// Union 合并包含元素 x 和 y 的两个集合
func (d *DisjointSets) Union(x, y int64) {
    d.Link(d.FindSet(x), d.FindSet(y))
}

package main

import "fmt"

// DisjointSets 泛型化后的结构体定义，支持任意可比较类型
type DisjointSets struct {
    ranks map[interface{}]int64 // rank值仍为 int64
    p map[interface{}]interface{} // 父节点现在可以是任意类型
}

// NewDisjointSets 创建并返回一个新的泛型 DisjointSets 实例
func NewDisjointSets() *DisjointSets {
    d := DisjointSets{map[interface{}]int64{}, map[interface{}]interface{}{}}
    return &d
}

// MakeSet 将元素 x 添加到不相交集中
func (d *DisjointSets) MakeSet(x interface{}) {
    // 确保 x 是可比较的，作为 map 的键
    d.p[x] = x
    d.ranks[x] = 0
}

// Link 根据秩合并两个根节点 x 和 y
func (d *DisjointSets) Link(x, y interface{}) {
    // x 和 y 必须是 FindSet 返回的根节点
    if d.ranks[x] > d.ranks[y] {
        d.p[y] = x
    } else {
        d.p[x] = y
        if d.ranks[x] == d.ranks[y] {
            d.ranks[y] += 1
        }
    }
}

// FindSet 查找元素 x 所属集合的代表元素，并进行路径压缩
func (d *DisjointSets) FindSet(x interface{}) interface{} {
    // 检查 x 是否已存在于集合中，若不存在则无法查找
    if _, ok := d.p[x]; !ok {
        // 可以选择在这里抛出错误或 MakeSet(x)
        // 为了教程简洁，假设调用前已 MakeSet
        return nil // 或者 panic("element not found")
    }

    if x != d.p[x] {
        d.p[x] = d.FindSet(d.p[x]) // 路径压缩
    }
    return d.p[x]
}

// Union 合并包含元素 x 和 y 的两个集合
func (d *DisjointSets) Union(x, y interface{}) {
    // 调用前需确保 x 和 y 均已 MakeSet
    rootX := d.FindSet(x)
    rootY := d.FindSet(y)

    if rootX != nil && rootY != nil && rootX != rootY {
        d.Link(rootX, rootY)
    }
}

func main() {
    // 示例使用：处理 int 类型
    dsInt := NewDisjointSets()
    dsInt.MakeSet(1)
    dsInt.MakeSet(2)
    dsInt.MakeSet(3)
    dsInt.MakeSet(4)

    dsInt.Union(1, 2)
    dsInt.Union(3, 4)
    dsInt.Union(2, 3)

    fmt.Printf("FindSet(1): %v\n", dsInt.FindSet(1)) // 预期为 1 或 4
    fmt.Printf("FindSet(2): %v\n", dsInt.FindSet(2))
    fmt.Printf("FindSet(3): %v\n", dsInt.FindSet(3))
    fmt.Printf("FindSet(4): %v\n", dsInt.FindSet(4))
    fmt.Println("---")

    // 示例使用：处理 string 类型
    dsString := NewDisjointSets()
    dsString.MakeSet("apple")
    dsString.MakeSet("banana")
    dsString.MakeSet("cherry")
    dsString.MakeSet("date")

    dsString.Union("apple", "banana")
    dsString.Union("cherry", "date")
    dsString.Union("banana", "cherry")

    fmt.Printf("FindSet(\"apple\"): %v\n", dsString.FindSet("apple")) // 预期为 "apple" 或 "date"
    fmt.Printf("FindSet(\"banana\"): %v\n", dsString.FindSet("banana"))
    fmt.Printf("FindSet(\"cherry\"): %v\n", dsString.FindSet("cherry"))
    fmt.Printf("FindSet(\"date\"): %v\n", dsString.FindSet("date"))
    fmt.Println("---")

    // 示例使用：处理 float64 类型
    dsFloat := NewDisjointSets()
    dsFloat.MakeSet(1.1)
    dsFloat.MakeSet(2.2)
    dsFloat.MakeSet(3.3)
    dsFloat.MakeSet(4.4)

    dsFloat.Union(1.1, 2.2)
    dsFloat.Union(3.3, 4.4)
    dsFloat.Union(2.2, 3.3)

    fmt.Printf("FindSet(1.1): %v\n", dsFloat.FindSet(1.1)) // 预期为 1.1 或 4.4
    fmt.Printf("FindSet(2.2): %v\n", dsFloat.FindSet(2.2))
    fmt.Printf("FindSet(3.3): %v\n", dsFloat.FindSet(3.3))
    fmt.Printf("FindSet(4.4): %v\n", dsFloat.FindSet(4.4))
}