# Java DFS, 4ms, single nested HashMap, 52 lines of code

• I was not able to see use graph to solve in the beginning because I failed to see the relationships and I am not familiar with the math behind this problem. After see some solutions, I made this answer my own. The idea is to search any path from symbol A to symbol B (DFS will do). The values to the vertices are ratios. When traversal the graph, multiply the rations you encountered as the result.

Hope it helps

``````    public void addEdge(String sa, String sb, double val, Map<String, Map<String, Double>> graph) {
Map<String, Double> vertex = graph.get(sa);
if (vertex == null) {
vertex = new HashMap<>();
graph.put(sa, vertex);
}
vertex.put(sb, val);
}

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {

Map<String, Map<String, Double>> graph = new HashMap<>();

for (int i  = 0; i < values.length; i++) {
String[] syms = equations[i];
String sym1 = syms[0];
String sym2 = syms[1];
addEdge(sym2, sym1, 1 / values[i], graph);
}

double[] rt = new double[queries.length];
for (int i = 0;i < queries.length; i++) {
String[] syms = queries[i];
String sym1 = syms[0];
String sym2 = syms[1];
rt[i] = countRatio(graph, sym1, sym2, new HashSet<>());
}
return rt;
}

private double countRatio(Map<String, Map<String, Double>> graph, String syma, String symb, Set<String> visited) {
Map<String, Double> vertex = graph.get(syma);
if (vertex == null) return -1;
if (syma.equals(symb)) return 1;
for (Map.Entry<String, Double> e : vertex.entrySet()) {
String sb = e.getKey();
Double ratio = e.getValue();
if (!visited.contains(sb)) {
double cr = countRatio(graph, sb, symb, visited);
if (cr != -1) {
double res = ratio * cr;
if (visited.contains(symb)) return res;
}
}
}
return -1;
}``````

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