Python实现并查集

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 '输入错误'