Build a weighted directed graph where edge (A, B) has weight val (A/B) and (B, A) has weight 1/val. Run DFS/BFS for queries.
from collections import defaultdict
def calcEquation(equations, values, queries):
graph = defaultdict(dict)
for (u, v), val in zip(equations, values):
graph[u][v] = val
graph[v][u] = 1.0 / val
def dfs(curr, target, visited, product):
if curr not in graph or curr in visited:
return -1.0
if curr == target:
return product
visited.add(curr)
for neighbor, val in graph[curr].items():
res = dfs(neighbor, target, visited, product * val)
if res != -1.0:
return res
return -1.0
return [dfs(q[0], q[1], set(), 1.0) for q in queries]class Solution {
public double[] calcEquation(List> equations, double[] values, List> queries) {
Map> graph = new HashMap<>();
for (int i = 0; i < equations.size(); i++) {
String u = equations.get(i).get(0);
String v = equations.get(i).get(1);
double val = values[i];
graph.computeIfAbsent(u, k -> new HashMap<>()).put(v, val);
graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, 1.0 / val);
}
double[] results = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
results[i] = dfs(queries.get(i).get(0), queries.get(i).get(1), new HashSet<>(), graph, 1.0);
}
return results;
}
private double dfs(String curr, String target, Set visited, Map> graph, double product) {
if (!graph.containsKey(curr) || visited.contains(curr)) return -1.0;
if (curr.equals(target)) return product;
visited.add(curr);
for (Map.Entry neighbor : graph.get(curr).entrySet()) {
double res = dfs(neighbor.getKey(), target, visited, graph, product * neighbor.getValue());
if (res != -1.0) return res;
}
return -1.0;
}
}