Why it works
- An arrow x → y with weight k says x / y = k, and the arrow back says y / x = 1 / k. Along a path the fractions chain: (p / r) × (r / s) = p / s, so the product of the weights is the answer.
- Depth-first search tries one arrow at a time; a branch that cannot reach the end, like u here, returns -1, and the walk goes on with the next arrow. visited keeps it from going round in circles.
- Only a variable that some equation names is in the graph, so a query about any other one is -1 straight away.
Complexity
Time O(q × (n + m)), where n is the number of variables, m the number of equations and q the number of queries: each query is one walk that visits a variable at most once. Memory O(n + m) for the graph and visited.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗