代码模版

结构

1
2
3
4
5
type UnionFind struct {
	parent []int
    rank []int
    count int 
}

初始化

1
2
3
4
5
6
7
8
9
func NewUnioinFind(n int) *UnionFind{
    parent := make([]int, n)
    rank := make([]int, n)
    for i := range parent{
        parent[i] = i
        rank[i] = 1
    }
    return &UnionFind{parent, rank, n}
}

查询(find)

1
2
3
4
5
6
7
func(uf *UnionFind)find(x int)int{
    //由于初始化时parent[i] = i，所以代表元的特点为paren[i]=i
    if uf.parent[x] != x{
        uf.parent[x] = uf.find(uf.parent[x]) //路径压缩
    }
    return uf.parent[x]
}

按秩合并（unite）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func(uf *UnionFind)unite(x, y int){
    xRoot, yRoot := uf.find(x), uf.find(y)
    if xRoot != yRoot {//进行合并
        uf.count--
        if uf.rank[yRoot] <= uf.rank[xRoot]{ //将y合并到x
            uf.parent[yRoot] = uf.parent[xRoot]
        }else{
            uf.parent[xRoot] = uf.parent[yRoot]
        }
        if uf.rank[xRoot] == uf.rank[yRoot]{
            uf.rank[xRoot]++
        }
    }
}