Equations are given in the format `A / B = k`

, where `A`

and `B`

are variables represented as strings, and `k`

is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return `-1.0`

.

**Example:**

Given `a / b = 2.0, b / c = 3.0.`

queries are: `a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .`

return `[6.0, 0.5, -1.0, 1.0, -1.0 ].`

The input is: `vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries `

, where `equations.size() == values.size()`

, and the values are positive. This represents the equations. Return `vector<double>`

.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: graph = dict() # Build graph for (a, b), value in zip(equations, values): graph[a] = graph.get(a, []) + [(b, value)] graph[b] = graph.get(b, []) + [(a, 1/value)] def check(source, target): # If there is any one number of the query didn't appear in the graph, answer certainly doesn't exist. if source not in graph or target not in graph: return -1.0 visited = set() stack = collections.deque([(source, 1.0)]) while stack: front, current = stack.popleft() if front == target: return current visited.add(front) for back, value in graph[front]: if back not in visited: stack.append((back, current * value)) return -1.0 return [check(source, target) for (source, target) in queries]