# 不帶權(quán)重的并查集
class UnionFindSet:
    def __init__(self):
        self.father = {} # key: 節(jié)點
    def add(self, x):
        if x not in self.father:
            self.father[x] = None
    # 查詢根節(jié)點的同時進行路徑壓縮
    def findRoot(self, x):
        root = x
        while self.father[root] is not None:
            root = self.father[root]
        # root為當前的根節(jié)點
        # 路徑壓縮
        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

# 帶權(quán)重的并查集
class UnionFindSet:
    def __init__(self):
        self.father={} # key:節(jié)點,value:father
        self.weights={} # 節(jié)點到父節(jié)點的權(quán)重
    def add(self, x):
        if x not in self.father:
            self.father[x] = None
            self.weights[x] = 1
    # 查詢根節(jié)點的同時進行路徑壓縮并修改權(quán)重,遞歸寫法
    def findRoot2(self, x):
        root = x
        # 順著x往上竄,一直找到x的祖先root
        while self.father[root] is not None:
            root = self.father[root]
        # root為x的根節(jié)點
        # 路徑壓縮并修改權(quán)重：迭代 改為 遞歸
        if x != root:
            # 再順著x往上竄一遍,一邊竄一邊把每個節(jié)點的父節(jié)點改成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 # 權(quán)重放大倍數(shù)
        # 順著x往上竄,一直找到x的祖先root
        while self.father[root] is not None:
            root = self.father[root]
            base *= self.weights[root] # 總倍數(shù)
        # root為x的根節(jié)點,路徑壓縮.
        while x != root:
            original_father = self.father[x]
            self.father[x] = root
            self.weights[x] *= base
            # 離根節(jié)點越近继榆，放大倍數(shù)越小滨巴。
            base /= self.weights[original_father]
            x = original_father
        return root

    def union(self, x, y, value):
        # value 為 x/y的值
        # 此處進行了查找，weights已經(jīng)改變了
        root_x, root_y = self.findRoot(x), self.findRoot(y)
        # x,y的根節(jié)點相等前翎，說明不需要合并
        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 = 基本單位
             記根節(jié)點為s = 1,也就是root_x
            """
            self.weights[root_x] = self.weights[y] * value / self.weights[x]
    # 判斷x,y是否在一個集合中已维，如果在一個集合中則返回除法的結(jié)果否則返回-1
    def isConnected(self, x, y):
        # 注意此處執(zhí)行了查詢斧蜕，修改了權(quán)重
        root_x ,root_y = self.findRoot(x), self.findRoot(y)
        if root_x != root_y: # 不在一個集合中
            return -1
        return self.weights[x] / self.weights[y]