# Easy AC DFS solution

• ``````public class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {

if(equations==null|| values==null || queries ==null || equations.length==0||
values.length==0||queries.length==0){
return new double[0];

}
int len = queries.length;
double[] result = new double[len];
//Create Graph
HashMap<String,HashMap<String,Double>> graph_map = new HashMap<String, HashMap<String, Double>>();
int eq_len = values.length;
for(int i=0;i<eq_len;i++){
String start = equations[i][0];
String end = equations[i][1];
double val = values[i];
if(!graph_map.containsKey(start)){
HashMap<String,Double> map =new HashMap<String, Double>();
map.put(end,val);
graph_map.put(start,map);
}else{
HashMap<String,Double> map = graph_map.get(start);
map.put(end,val);
graph_map.put(start,map);
}
if(!graph_map.containsKey(end)){
HashMap<String,Double> map =new HashMap<String, Double>();
map.put(start,1/val);
graph_map.put(end,map);
}else{
HashMap<String,Double> map = graph_map.get(end);
map.put(start,1/val);
graph_map.put(end,map);
}

}
for(int i=0;i<queries.length;i++){
String start = queries[i][0];
String end =queries[i][1];

if(!graph_map.containsKey(start)||!graph_map.containsKey(end)){
result[i]=-1.0;
}else if(start.equals(end)){
result[i]=1.0;
}
else{
double val =DFS(graph_map,1.0,end,start,new HashSet<String>());
if(val==0.0){
result[i]=-1.0;
}
else {
result[i]=val;
}
}
}

return result;

}

public double DFS(HashMap<String,HashMap<String,Double>> graph, double val, String end, String start, HashSet<String> set){
HashMap<String ,Double> map = graph.get(start);
//Set is used to detect cycle
double temp=0.0;
if(start.equals(end)){
return 1.0;
}

if(map.containsKey(end)){
return val*map.get(end);
}else{

for(String s: map.keySet()){
if(!set.contains(s)){
double t = DFS(graph,val*map.get(s),end,s,set);
if(t !=0.0){
temp=t;
break;
}
}

}
}
set.remove(start);
return temp;
}

}``````

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