330. Evaluate Division
You are given a set of known ratios between named variables: equations[i] = [A, B] paired with values[i] means A / B = values[i], where each variable is a lowercase string name. Using only these facts, answer a list of queries, where queries[j] = [C, D] asks for the numeric value of C / D.
Return one number per query. If a query cannot be deduced — either variable never appeared in any equation, or the two variables belong to groups with no chain of equations between them — answer -1.0. A variable divided by itself is 1.0 only if that variable appeared in some equation; asking about a completely unknown name still yields -1.0.
The equations are guaranteed consistent (no contradictions) and no variable ever equals zero. Think of each equation as a weighted edge in a graph: A → B with weight values[i] and B → A with weight 1 / values[i]. A query is then the product of weights along any path.
Canonical output: the judge prints every answer with exactly five decimal places (so 6 prints as 6.00000 and an undeducible query as -1.00000); the test data is chosen so all correct algorithms agree at that precision.
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.00000, 0.50000, -1.00000, 1.00000, -1.00000]
Explanation: From a/b = 2 and b/c = 3, chaining gives a/c = 2 × 3 = 6 and inverting gives b/a = 1/2. Variable e never appeared, so a/e is unknowable; a/a = 1 since a is known; x/x = -1 because x is a name we have never seen.
Example 2:
Input: equations = [["a","b"]], values = [0.5], queries = [["b","a"],["a","b"],["a","c"]]
Output: [2.00000, 0.50000, -1.00000]
Explanation: a/b = 0.5, so the reverse ratio b/a is 1/0.5 = 2. The variable c is not connected to anything, so a/c cannot be computed.
Constraints:
- 1 ≤ equations.length ≤ 20
- 1 ≤ queries.length ≤ 20
- 0.0 < values[i] ≤ 20.0
- Variable names are 1 to 5 lowercase English letters.
- The given equations are internally consistent.
Hints:
Treat each variable as a graph node. The equation a/b = v is an edge a → b with weight v — and, crucially, an implicit reverse edge b → a with weight 1/v. What does a query become in this picture?
A query c/d is the product of edge weights along any path from c to d (consistency guarantees all paths agree). BFS or DFS per query works. To answer many queries faster, use a weighted union-find: store each node's ratio to its component root and compare roots.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: equations = [["a","b"],["b","c"]], values = [2.0, 3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Expected output: [6.00000, 0.50000, -1.00000, 1.00000, -1.00000]