LeetCode专题】Evaluate Division

class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        # construct a bi-directional graph with a nested dict
        graph = dict()
        for idx in range(0, len(equations)):
            equation = equations[idx]
            numerator = equation[0]
            denominator = equation[1]
            if graph.get(denominator) is None:
                # self connecting
                graph[denominator] = {denominator: 1.0}

            if graph.get(numerator) is None:
                graph[numerator] = {numerator: 1.0}

            graph[numerator][denominator] = values[idx]
            graph[denominator][numerator] = 1 / values[idx]

        results = list()
        for query in queries:
            visited = set()
            val, _ = self.dfs(graph, visited, query[0], query[1])
            results.append(val)

        return results

    def dfs(self, graph, visited, src, dst):
        visited.add(src)
        src_node = graph.get(src)
        if src_node is None:
            return -1.0, False
        val = src_node.get(dst)
        if val is not None:
            return val, True
        for connection in src_node:
            if connection in visited:
                continue
            val, exists = self.dfs(graph, visited, connection, dst)
            if not exists:
                continue
            return src_node[connection] * val, True
        return -1.0, False