Evaluate Division

Problem

You are given a list of equations, each a pair of variable names [a, b], and a parallel list values where values[i] states that a / b == values[i]. Then you are given queries, each a pair [c, d]. For each query return the value of c / d if it can be deduced from the equations, otherwise -1.0. A variable that never appears in any equation is unknown, so any query involving it returns -1.0. All given values are positive, and no variable is ever zero.

• There are at most a few dozen equations and a few dozen queries, values[i] > 0.
• Variable names are non-empty strings of lowercase letters and digits.

Examples

• equations = [["p","q"],["q","r"]], values = [4.0, 5.0], queries = [["p","r"],["q","p"],["p","z"],["p","p"],["m","m"]] → [20.0, 0.25, -1.0, 1.0, -1.0]. p/r = (p/q)(q/r) = 20; q/p is the inverse of p/q; z and m are unknown.
• equations = [["p","q"]], values = [0.25], queries = [["q","p"]] → [4.0].
• equations = [["p","q"],["r","s"]], values = [2.0, 3.0], queries = [["p","s"]] → [-1.0]. Two separate components; no chain of facts links them.

Hints

1. If you know a/b and b/c, how do you get a/c? What does that operation look like if you draw the variables as nodes?
2. Each equation gives you two directed edges with weights that are reciprocals of each other.
3. For each query, search (DFS/BFS) from the numerator to the denominator, multiplying edge weights along the path. Or use a weighted union-find that stores each variable's ratio to its root.