Build the graph from equations, then BFS for each query. Multiply weights along the path.
function calcEquation(equations, values, queries):
graph = empty adjacency map
for i from 0 to equations.length - 1:
a = equations[i][0]
b = equations[i][1]
graph[a].append((b, values[i]))
graph[b].append((a, 1.0 / values[i]))
function bfs(src, dst):
if src not in graph or dst not in graph:
return -1.0
if src == dst:
return 1.0
visited = set()
queue = [(src, 1.0)]
visited.add(src)
while queue is not empty:
node, product = queue.dequeue()
for neighbor, weight in graph[node]:
if neighbor == dst:
return product * weight
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue((neighbor, product * weight))
return -1.0
results = []
for each (x, y) in queries:
results.append(bfs(x, y))
return results