class bingchaji():
node = set()
parent = dict()
parent_size = dict()
def __init__(self, a):
for i in a:
self.node.add(i)
self.parent[i] = i
self.parent_size[i] = 1
print(self.parent_size)
def find_father(self, x):
p = set()
while self.parent.get(x) != x:
p.add(x)
x = self.parent.get(x)
for i in p:
self.parent[i] = x
return x
def is_same(self, x, y):
if self.node.__contains__(x) and self.node.__contains__(y):
return self.find_father(x) == self.find_father(y)
else:
return
def union(self, x, y):
if self.node.__contains__(x) and self.node.__contains__(y):
x_father = self.find_father(x)
y_father = self.find_father(y)
x_size = self.parent_size.get(x_father)
y_size = self.parent_size.get(y_father)
if x_father != y_father:
if x_size > y_size:
self.parent[y_father] = x_father
self.parent_size[x_father] += y_size
del self.parent_size[y_father]
else:
self.parent[x_father] = y_father
self.parent_size[y_father] += x_size
del self.parent_size[x_father]
else:
return '输入错误'
