175. Evaluate Division

Medium · Graph

You are given a list of equations in the form `A / B = k`, where `A` and `B` are variable name strings and `k` is a real number. You are also given a list of queries, each asking for the value of `C / D`. Return the answers to all queries. If the answer does not exist (the variables are unknown or the path cannot be determined), return `-1.0` for that query.

Model the problem as a weighted directed graph: for each equation `A / B = k`, add an edge from `A` to `B` with weight `k`, and an edge from `B` to `A` with weight `1/k`. To answer a query `C / D`, perform a BFS/DFS from node `C` to node `D`, multiplying edge weights along the path.

Note: The input is an array `[equations, values, queries]` where `equations` is an array of `[A, B]` pairs, `values` is an array of corresponding `k` values, and `queries` is an array of `[C, D]` pairs.

Examples

Example 1
Input: equations = [["a","b"],["b","c"]], values = [2.0, 3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.0, 0.5, -1.0, 1.0, -1.0]
Explanation: a/b=2, b/c=3 so a/c=6; b/a=1/2=0.5; 'e' is unknown so -1.0; a/a=1.0; 'x' is unknown so -1.0.
Example 2
Input: equations = [["a","b"],["c","d"]], values = [2.0, 3.0], queries = [["a","c"],["b","d"],["a","a"]]
Output: [-1.0, -1.0, 1.0]
Explanation: a and b are disconnected from c and d, so a/c and b/d are -1.0. a/a=1.0.

Constraints