# Java HashMap DFS solution, 3ms

• ``````public class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
HashMap<String, Double> nums = new HashMap();
HashMap<String, List<Integer>> edges = new HashMap();
HashMap<String, Integer> group = new HashMap();

// build the graph, count the in-degree of each node
for (int i = 0; i < values.length; i++) {
String[] curPair = equations[i];
// make undirected graph directed
if (nums.containsKey(curPair[1]) && nums.get(curPair[1]) < 0.0) {
String temp = curPair[0];
curPair[0] = curPair[1];
curPair[1] = temp;
values[i] = 1 / values[i];
}
String start = curPair[0], end = curPair[1];
if (!nums.containsKey(start)) {
nums.put(start, 0.0);
}
nums.put(end, nums.getOrDefault(end, 0.0) - 1.0);
List<Integer> edge = edges.get(start);
if (edge == null) {
edge = new ArrayList();
edges.put(start, edge);
}
}

// iterate the graph via DFS, group the nodes and calculate the value of each node
int groupId = 0;
for (Map.Entry<String, Double> numEntry : nums.entrySet()) {
if (numEntry.getValue() == 0.0) {
numEntry.setValue(1.0);
String start = numEntry.getKey();
dfs(nums, edges, group, start, groupId++, equations, values);
}
}

// make queries O(N)
double[] result = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
String s = queries[i][0], e = queries[i][1];
result[i] = -1.0;
if (group.get(s) != null && group.get(s) == group.get(e)) {
result[i] = nums.get(s) / nums.get(e);
}
}
return result;
}

private void dfs(HashMap<String, Double> nums, HashMap<String, List<Integer>> edges , HashMap<String, Integer> group, String start, int groupId, String[][] equations, double[] values) {

group.put(start, groupId);
List<Integer> nextEdges = edges.get(start);
if (nextEdges != null) {
for (int edgeIdx : nextEdges) {
String s = equations[edgeIdx][0], e = equations[edgeIdx][1];
nums.put(e, nums.get(s) / values[edgeIdx]);
dfs(nums, edges, group, e, groupId, equations, values);
}
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.