399.除法求值

https://leetcode-cn.com/problems/evaluate-division/

一、并查集+压缩路径

参考https://leetcode-cn.com/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/

难点在于压缩路径

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 到根节点的权值
        self.weight = [1.0] * totalNodes
    # 因为是将x指向y，即y离终点更近，因此以y的根rootY为rootX的根
    def union(self, x, y, value):
        rootX = self.find(x)
        rootY = self.find(y)
        # 若连通则跳过
        if rootX == rootY:
            return
        self.parents[rootX] = rootY

        self.weight[rootX] = self.weight[y] * value / self.weight[x]

    # 查找最终的根
    def find(self, node):
        # 尾递归，最终路径上所有节点的父结点都指向根
        if node != self.parents[node]:
            # 先记录本层的父，用于计算权重
            old = self.parents[node]
            # 更新本层node的父
            self.parents[node] = self.find(self.parents[node])
            # 更新权重
            self.weight[node] *= self.weight[old]
        return self.parents[node]   #本层node的父传给上一层

class Solution:
    def calcEquation(self, equations, values, queries):
        map = {}
        n = 0
        # 每个变量映射到0~n-1，作为并查集的结点
        for x, y in equations:
            if x not in map:
                map[x] = n
                n += 1
            if y not in map:
                map[y] = n
                n += 1
        uf = UnionFind(n)
        # 处理所有顶点和边
        for i in range(len(equations)):
            # 变量转换为节点
            x, y = equations[i][0], equations[i][1]
            nodeX, nodeY =  map.get(x), map.get(y)
            value = values[i]
            # 连通两个点
            uf.union(nodeX, nodeY, value)

        res = []
        for x, y in queries:
            # 变量有一个不存在，直接返回-1
            if x not in map or y not in map:
                res.append(-1.0)
            else:
                nodeX, nodeY = map.get(x), map.get(y)
                rootX = uf.find(nodeX)
                rootY = uf.find(nodeY)
                if rootX == rootY:
                    res.append(uf.weight[nodeX] / uf.weight[nodeY])
                else:   # 若不连通，直接返回-1
                    res.append(-1.0)
        return res