福
福

雨辰枫司的小栈

并查集

  • ~4.12K 字
  • 条评论
  1. 1. 并查集
  2. 2. 带权并查集

并查集

并查集是一种树形的数据结构，用于处理一些不相交的合并与查询问题。

例如：

有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

查询 x~i~ 和 y~i~ 是否在同一个集合

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: #disjointed sets union
    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: #disjointed sets union
    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)

,