并查集
#数据结构#并查集 2023-12-31

并查集

定义

并查集主要用于解决元素分组以及管理一系列不相交的集合，并支持：

  • 合并，将两个不相交的集合合并成一个
  • 查询，查询两个元素是否存在于同一个集合中

基本使用

初始化

不需要深度

将所有元素的根节点都设为自己

1
2
3
4
5
6
7
8
9
func SimpleInit(n int) (disjointSet []int) {
	disjointSet = make([]int, n)

	for i := range disjointSet {
		disjointSet[i] = i
	}

	return
}

需要深度（最常用

深度就是以当前节点为根节点的树的深度，方便之后按深度合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type DisjointSet struct {
	Set  []int
	Rank []int
}

func Init(n int) DisjointSet{
	var set = make([]int, n)
	var rank = make([]int, n)
	
	for i := range set{
		set[i] = i
		rank[i] = 1 // 初始时都是 1 层
	}
	
	return DisjointSet{
		set,
		rank,
	}
}

查找

简单查找

1
2
3
4
5
6
7
func SimpleFind(disjointSet []int, val int) int {
	if disjointSet[val] == val {
		return val
	}

	return SimpleFind(disjointSet, disjointSet[val])
}

路径压缩

我们将传入的 val 直接指向根节点，相当于一个两层的树。

1
2
3
4
5
6
7
8
func CompressFind(disjointSet []int, val int) int {
	if disjointSet[val] == val {
		return val
	}

	disjointSet[val] = CompressFind(disjointSet, val)
	return disjointSet[val]
}

合并

简单合并

将当前元素的根节点更新为 j 的根节点即可。

1
2
3
func SimpleMerge(disjointSet []int, i, j int) {
	disjointSet[SimpleFind(disjointSet, i)] = j
}

或者

1
2
3
func CompressMerge(disjointSet []int, i, j int) {
	disjointSet[CompressFind(disjointSet, i)] = CompressFind(disjointSet, j)
}

按深度合并

1

Reference

算法学习笔记(1) : 并查集 - 知乎 (zhihu.com)