Evaluate Division

Intuition

A division a / b = value is really a directed connection from a to b with a weight equal to value, and the reverse connection from b to a naturally carries weight 1 / value. Once every equation is expressed this way, evaluating a query becomes the task of finding a path from the source variable to the target variable. Multiplying all the edge weights along that path telescopes the intermediate variables and leaves exactly the ratio we want. A depth-first search explores possible paths, and marking visited nodes prevents cycles from looping forever. If the search never reaches the target, or if either variable was never seen, the query is undetermined and we return -1.0.

Algorithm walkthrough

1. 1Build an adjacency structure where each variable maps to its neighbors together with the division ratio on that edge.
2. 2For every equation add a forward edge weighted by the value and a backward edge weighted by its reciprocal.
3. 3For each query, first confirm both variables exist in the graph; if either is missing, record -1.0.
4. 4Run a depth-first search from the source, carrying the accumulated product and a visited set to avoid revisiting nodes.
5. 5When the search reaches the target, multiply the current edge weight by the result returned from the recursion and propagate it back up.
6. 6If no neighbor leads to the target, return -1.0 so the caller knows the query is unresolved.

Implementation

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

        def dfs(src, dst, visited):
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited.add(src)
            for neighbor, weight in graph[src].items():
                if neighbor in visited:
                    continue
                sub = dfs(neighbor, dst, visited)
                if sub != -1.0:
                    return weight * sub
            return -1.0

        result = []
        for c, d in queries:
            result.append(dfs(c, d, set()))
        return result