You are given equations like a divided by b equals 2. Answer queries like a divided by c, or return minus 1 if the answer cannot be determined.
DSA Animator › DSA Revision › Graph › Evaluate Division
Remember: ratios become edge weights, and a path multiplies them. The reverse edge always has the reciprocal weight. The video solves Evaluate Division (LeetCode 399, Medium) with the Weighted Graph DFS pattern from the Graph topic, and you can replay every step in the interactive Evaluate Division animation.
You are given equations like a divided by b equals 2. Answer queries like a divided by c, or return minus 1 if the answer cannot be determined.
With a over b equal to 2 and b over c equal to 3, the query a over c is 6. b over a is 0.5, a over e is minus 1 because e is unknown, and a over a is 1.
Trying to solve the equations algebraically is complicated. Instead, picture every variable as a node in a graph.
For a over b equal to 2, add an edge from a to b with weight 2, and from b to a with weight one half. The answer to x over y is the product of the weights along any path from x to y. This works because the middle variables cancel out: a over b times b over c is a over c. If either variable is unknown, or no path exists, the answer is minus 1.
The graph has the edges a to b with 2, b to c with 3, and the two reverse edges with one half and one third. For a over c, walk from a to b, the product is 2. Then from b to c, the product becomes 2 times 3, which is 6. For b over a, the single reverse edge gives 0.5. a over e is minus 1, because e never appears. a over a is 1, because a known variable divided by itself is 1.
In code, build a map from each variable to a map of neighbours and weights. For each query, return minus 1 if either variable is missing. Otherwise run a DFS from the start, carrying the product, and return it when the target is reached. Each query is O of v plus e.
Remember: ratios become edge weights, and a path multiplies them. The reverse edge always has the reciprocal weight.