class UnionFindSet(object):
def __init__(self, nodes):
'''
初始化并查集
'''
# 记录每个节点的父节点
self.fatherMap = {}
# 各集合的数量
self.setNumMap = {}
# 初始化, 每个节点自成一派
for node in nodes:
self.fatherMap[node] = node
self.setNumMap[node] = 1
def findFather(self, node):
'''
递归逻辑:返回当前节点的父节点;
'''
father = self.fatherMap[node]
if (node != father):
father = self.findFather(father)
# 路径压缩
self.fatherMap[node] = father
return father
def isSameSet(self, a, b):
'''
判断两个节点a和b是否属于同一集合
'''
return self.findFather(a) == self.findFather(b)
def union(self, a, b):
'''
合并集合a到集合b中
'''
if a is None or b is None:
return
aFather=self.findFather(a)
bFather = self.findFather(b)
if (aFather != bFather):
# 获取a,b集合的数量
aNum=self.setNumMap[aFather]
bNum=self.setNumMap[bFather]
# a集合加入b的集合中
self.fatherMap[aFather]=bFather
self.setNumMap[bFather]=aNum + bNum
# 删除aFather对应的人数纪录
self.setNumMap.pop(aFather)
