399. Evaluate Division

link

It's an undirected acyclic graph. We can use union find first, to find if two variable are connected.

Since the equations is just few, we can just use dfs method.

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:

        M = defaultdict(list)

        for i, [v1, v2] in enumerate(equations):
            M[v1].append((v2, values[i]))
            M[v2].append((v1, 1 / values[i]))

        
        def find(start, end):

            dq = deque(M[start])

            S = set()
            while dq:

                lens = len(dq)
                for _ in range(lens):
                    v, w = dq.popleft()

                    if v == end:
                        return w
                    
                    if v in S:
                        continue
                    
                    S.add(v)

                    for [vv, ww] in M[v]:
                        dq.append((vv, w * ww))

            return -1

        res = []

        for [v1, v2] in queries:
            res.append(find(v1, v2))


        return res