399. Evaluate Division

[fockspaces]

graph problem, according to fraction multiply rules, we can think (a / b) = 2 as a -> b take 2 unit (c / b) take 3 unit then (a / b) (c / b) equals to a -> b -> c, that will take 2 3 = 6 unit when we want to traverse back from c -> b -> a, it can be seen as (1/3) * (1/2) = 1 / 6

1. create bi-direction graph, for src to dest, weight is k, dest to src, weight is 1/k
2. create DFS function that will return the total distance from src to target if find the target
3. for each query, do DFS and get the return results

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        def DFS(root, value, target, visited):
            if root == target and root in graph.keys():
                return value
            visited.add(root)
            for neighbor, distance in graph.get(root, {}).items():
                if neighbor not in visited:
                    result = DFS(neighbor, value * distance, target, visited)
                    if result != -1:
                        return result
            return -1

        graph = {}
        for (numerator, denominator), value in zip(equations, values):
            if numerator not in graph:
                graph[numerator] = {}
            if denominator not in graph:
                graph[denominator] = {}
            graph[numerator][denominator] = value
            graph[denominator][numerator] = 1 / value

        results = []
        for src, target in queries:
            results.append(DFS(src, 1, target, set()))
        return results