# 不带权重的并查集
class UnionFindSet:
def __init__(self):
self.father = {} # key: 节点
def add(self, x):
if x not in self.father:
self.father[x] = None
# 查询根节点的同时进行路径压缩
def findRoot(self, x):
root = x
while self.father[root] is not None:
root = self.father[root]
# root为当前的根节点
# 路径压缩
if x != root:
original_father = self.father[x]
root = self.findRoot(original_father)
self.father[x] = root
return root
def union(self, x, y):
# 此处进行了查找
root_x, root_y = self.findRoot(x), self.findRoot(y)
if root_x != root_y:
self.father[root_x] = root_y
# 判断xy是否在一个集合中
def isConnected(self, x, y):
root_x ,root_y = self.findRoot(x), self.findRoot(y)
if root_x != root_y: # 不在一个集合中
return False
return True
# 带权重的并查集
class UnionFindSet:
def __init__(self):
self.father={} # key:节点,value:father
self.weights={} # 节点到父节点的权重
def add(self, x):
if x not in self.father:
self.father[x] = None
self.weights[x] = 1
# 查询根节点的同时进行路径压缩并修改权重,递归写法
def findRoot2(self, x):
root = x
# 顺着x往上窜,一直找到x的祖先root
while self.father[root] is not None:
root = self.father[root]
# root为x的根节点
# 路径压缩并修改权重：迭代 改为 递归
if x != root:
# 再顺着x往上窜一遍,一边窜一边把每个节点的父节点改成root
original_father = self.father[x]
root = self.findRoot(original_father)# 递归的方式往上找
self.father[x] = root
self.weights[x] = self.weights[x] * self.weights[original_father]
return root
# 迭代写法
def findRoot(self, x):
root = x
base = 1 # 权重放大倍数
# 顺着x往上窜,一直找到x的祖先root
while self.father[root] is not None:
root = self.father[root]
base *= self.weights[root] # 总倍数
# root为x的根节点,路径压缩.
while x != root:
original_father = self.father[x]
self.father[x] = root
self.weights[x] *= base
# 离根节点越近，放大倍数越小。
base /= self.weights[original_father]
x = original_father
return root
def union(self, x, y, value):
# value 为 x/y的值
# 此处进行了查找，weights已经改变了
root_x, root_y = self.findRoot(x), self.findRoot(y)
# x,y的根节点相等，说明不需要合并
if root_x == root_y:
return
# x指向y或者y指向x都行，整个并查集都一致就行
if root_x != root_y:
self.father[root_x] = root_y
"""
这个公式需要推导
x/y = 2 ==> 2*y/x = 基本单位
记根节点为s = 1,也就是root_x
"""
self.weights[root_x] = self.weights[y] * value / self.weights[x]
# 判断x,y是否在一个集合中，如果在一个集合中则返回除法的结果否则返回-1
def isConnected(self, x, y):
# 注意此处执行了查询，修改了权重
root_x ,root_y = self.findRoot(x), self.findRoot(y)
if root_x != root_y: # 不在一个集合中
return -1
return self.weights[x] / self.weights[y]
