首先

在表达表示素集合数据结构时，Union-Find非常方便。在这里，我们将使用Go语言创建Union-Find。请注意，我们不会特别提及Union-Find本身。

需要什么功能

我认为以下功能是必要的。

• ある要素aの所属するグループを返す

 

• ある要素aの所属するグループ内の要素数(木のサイズ)を返す

 

• ある要素aの所属する[グループA] と ある要素bの所属する[グループB] を合体する

 

ある要素aとある要素bが同じグループに所属するかどうかを返す

执行

让我们创建一个具有上述功能的结构体。

type UnionFind struct {
    par []int
}

/* コンストラクタ */
func newUnionFind(N int) *UnionFind {
    u := new(UnionFind)
    u.par = make([]int, N)
    for i := range u.par {
        u.par[i] = -1
    }
    return u
}

/* xの所属するグループを返す */
func (u UnionFind) root(x int) int {
    if u.par[x] < 0 {
        return x
    }
    u.par[x] = u.root(u.par[x])
    return u.par[x]
}

/* xの所属するグループ と yの所属するグループ を合体する */
func (u UnionFind) unite(x, y int) {
    xr := u.root(x)
    yr := u.root(y)
    if xr == yr {
        return
    }
    u.par[yr] += u.par[xr]
    u.par[xr] = yr
}

/* xとyが同じグループに所属するかどうかを返す */
func (u UnionFind) same(x, y int) bool {
    if u.root(x) == u.root(y) {
        return true
    }
    return false
}

/* xの所属するグループの木の大きさを返す */
func (u UnionFind) size(x int) int {
    return -u.par[u.root(x)]
}

利用 (lì – utilize/ make use of

func main() {
    // インスタンスの生成
    u := newUnionFind(N)

    // 各メソッドの利用
    u.unite(a, b)
    u.same(a, b)
    u.size(a)
    u.root(a)
}

关于内容

家庭树木的要素中，如果将该树的大小表示为N，则父节点的值为$N \times (-1)$，子节点的值则是其所属树木的父节点的值。

因此，如果元素是负数，那么可以确定它是父节点，并将其转换回正数以得到该树的大小。