//construct a Edge class to store both weight and value

class Edge {

double weight;

String val;

public Edge(double w, String s){

this.weight = w;

this.val = s;

}

}

public class Solution {

```
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
if (queries.length == 0) {
return new double[0];
}
double[] rst = new double[queries.length];
HashMap<String, HashSet<Edge>> graph = new HashMap<>();
//vertices
for (String[] equ : equations) {
graph.putIfAbsent(equ[0], new HashSet<Edge>());
graph.putIfAbsent(equ[1], new HashSet<Edge>());
}
//edges
for (int i = 0; i < values.length; i++) {
String[] equ = equations[i];
double weight = values[i];
graph.get(equ[0]).add(new Edge(weight, equ[1]));
graph.get(equ[1]).add(new Edge(1 / weight, equ[0]));
}
for (int i = 0; i < queries.length; i++) {
String cur = queries[i][0];
String target = queries[i][1];
if (graph.get(cur) == null || graph.get(target) == null) {//characters not showing up
rst[i] = -1.0;
} else if (cur.equals(target)) {//same characters
rst[i] = 1.0;
} else {
double answer = dfs(cur, target, graph, 1, cur);
rst[i] = answer;
}
}
return rst;
}
//use a parent to prevent thrashing
public double dfs(String cur, String target, HashMap<String, HashSet<Edge>> graph, double val, String parent) {
HashSet<Edge> neighbor = graph.get(cur);
for (Edge edge : neighbor) {
if (!edge.val.equals(parent)) {
val = val * edge.weight;
if (edge.val.equals(target)) {
return val;
} else {
double dfs = dfs(edge.val, target, graph, val, cur);
if (dfs != -1) {
return dfs;
}
}
//backtracking
val = val / edge.weight;
}
}
return -1;
}
```

}