[5/20] 399. Evaluate Division

# Time Complexity: O(n + e), Space Compleixty: O(n + e)

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = defaultdict(dict)
        for (u, v), val in zip(equations, values):
            graph[u][v] = val
            graph[v][u] = 1 / val

        def dfs(u, v, visited):
            if (v not in graph):
                return -1.0
            elif (u == v):
                return 1
            elif (v in graph[u]):
                return graph[u][v]

            visited.add(u)
            for c in graph[u]:
                if c not in visited:
                    cToV = dfs(c, v, visited)
                    if (cToV != -1.0):
                        graph[u][v] = graph[u][c] * cToV
                        return graph[u][v]
            return -1.0

        return [dfs(u, v, set()) for (u, v) in queries]