# Leetcode 399. Evaluate Division

## 題解

### Union Find (待補)

### DFS

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = {}
        for i, data in enumerate(equations):
            src, target = data
            if src not in graph:
                graph[src] = {}
            if target not in graph:
                graph[target] = {}
            graph[src][target] = values[i]
            graph[target][src] = 1 / values[i]
        
        def dfs(src, target, visits, ans):
            if src not in graph or target not in graph or src in visits:
                return -1
            visits.add(src)
            if src == target:
                return ans
            for nei in graph[src]:
                res = dfs(nei, target, visits, ans * graph[src][nei])
                if res != -1: # 是答案才返回
                    return res
            return -1
        
        return [dfs(q[0], q[1], set(), 1) for q in queries]