并查集
并查集是一种树形的数据结构，用于处理一些不相交的合并与查询问题。
例如：
有n个元素，分属不同的n个集合:
主要有两种操作，一种是合并，另一个就是查询:
x 和 y 合并：将 x 和 y 的集合合并成一个大集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| graph TD
subgraph y
4
5
6
end
subgraph x
1
2
3
end
subgraph xy
1 --> 1'[1]
2 --> 2'[2]
3 --> 3'[3]
4 --> 4'[4]
5 --> 5'[5]
6 --> 6'[6]
end
|
查询 xi 和 yi 是否在同一个集合
1
2
3
4
5
6
7
8
9
10
11
| graph TD
subgraph y
4
5
6
end
subgraph x
1
2
3
end
|
查询 1 ，2 返回 true 。查询 1 ，4 返回 false。
首先用数组存储这样的数据，需要传入一个数据数量。开始的父结点都是自己
1
2
3
4
5
6
7
| graph TD
1 --> 1
2 --> 2
3 --> 3
4 --> 4
5 --> 5
6 --> 6
|
1
2
| def __init__(self,size:int):
self.arr = list(range(size))
|
接着定义一个查找父结点的方法(私有)
1
2
3
4
5
| def __findHead(self,num:int) -> int:
if num == self.arr[num]:
return num
self.arr[num] = self.__findHead(self.arr[num])
return self.arr[num]
|
压缩路径：在遍历的过程中尽量将该节点的数值直接定义为根节点，这样可以使下一次查找更方便
1
2
3
4
5
6
7
| graph LR
subgraph 后来
1' & 2' & 3' --> 4'
end
subgraph 原先
1 --> 2 --> 3 --> 4
end
|
接着定义一个合并集合的方法,就将A的父结点的父结点设置为B的父结点
1
2
3
4
| def merge(self,a,b) -> None:
aHead = self.__findHead(a)
bHead = self.__findHead(b)
self.arr[aHead] = bHead
|
还有一个查询方法，如果A ，B 两个父结点相同证明在同一个集合，反之则不在同一个集合
1
2
3
4
| def find(self,a,b) -> bool:
aHead = self.__findHead(a)
bHead = self.__findHead(b)
return aHead == bHead
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class DSU:
def __init__(self,size:int):
self.arr = list(range(size))
def __findHead(self,num:int) -> int:
if num == self.arr[num]:
return num
self.arr[num] = self.__findHead(self.arr[num])
return self.arr[num]
def merge(self,a,b) -> None:
aHead = self.__findHead(a)
bHead = self.__findHead(b)
self.arr[aHead] = bHead
def find(self,a,b) -> bool:
aHead = self.__findHead(a)
bHead = self.__findHead(b)
return aHead == bHead
|
带权并查集
如果两个节点之间存在某种关系，则需要一个能维护这种关系的并查集
1
2
3
4
5
6
7
| graph LR
subgraph B
4 --"re[4]"--> 5 --"re[5]"-->6
end
subgraph A
1 --"re[1]"--> 2 --"re[2]"-->3
end
|
与普通的并查集不同的是它们之间存在着某种关系，可以用一个 re 数组来记录当前节点和父结点的关系。
1
2
3
| def __init__(self,size:int):
self.arr = list(range(size))
self.re = [0] * size
|
压缩路径时将节点的权值更新，更新时可以用向量法来解决
1
2
3
| graph LR
a --"re[a]"--> b --"re[b]"--> c
a'[a] --"re[a] + re[b]"-->c'[c]
|
所以在查找父结点时更新路径加上re[a] = re[a] + re[b]就可以了
1
2
3
4
5
6
7
| def __findHead(self,num:int) -> int:
if num == self.arr[num]:
return num
father = self.arr[num]
self.arr[num] = self.__findHead(self.arr[num])
self.re[num] = self.re[num] + self.re[father]
return self.arr[num]
|
合并时将节点的权值加上即可，具体方法还是用向量
1
2
3
4
5
6
7
8
9
| graph TD
subgraph B
2 --"re[2]"--> 1
end
subgraph A
4 --"re[4]"--> 3
end
3 --"- re[4] + weights + re[2]"-->1
4 --"weights"--> 2
|
1
2
3
4
5
| def merge(self,a,b,weights) -> None:
aHead = self.__findHead(a)
bHead = self.__findHead(b)
self.re[aHead] = self.re[b] + weights - self.re[a]
self.arr[aHead] = bHead
|
查找不变
1
2
3
4
| def find(self,a,b) -> bool:
aHead = self.__findHead(a)
bHead = self.__findHead(b)
return aHead == bHead
|
如果要分类，加上一个mod（分类数目）就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class DSU:
def __init__(self,size:int,mod = 0):
self.arr = list(range(size))
self.re = [0] * size
self.size = size
self.mod = mod
if mod <= 0:
self.mod = size
def __findHead(self,num:int) -> int:
if num == self.arr[num]:
return num
father = self.arr[num]
self.arr[num] = self.__findHead(self.arr[num])
self.re[num] = (self.re[num] + self.re[father]) % self.mod
return self.arr[num]
def merge(self,a,b,weights) -> None:
aHead = self.__findHead(a)
bHead = self.__findHead(b)
self.arr[aHead] = bHead
self.re[aHead] = (self.re[b] + weights - self.re[a] + self.mod)%self.mod
def find(self,a,b) -> bool:
aHead = self.__findHead(a)
bHead = self.__findHead(b)
return aHead == bHead
def findHead(self,num:int) -> int:
return self.__findHead(num)
|