AC Java Graph + DFS

• Accepted Java code using Graph + DFS

``````	private class Node{
private Map<String, Double> nextNodes;
private boolean isVisit;
private Node(){
this.nextNodes = new HashMap<String, Double>();
this.isVisit = false;
}
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
if(equations.length == 0) return null;
double[] res = new double[queries.length];
Map<String, Node> graph = new HashMap<String, Node>();
for(int i = 0; i < equations.length; i++){
if(!graph.containsKey(equations[i][0])) graph.put(equations[i][0], new Node());
graph.get(equations[i][0]).nextNodes.put(equations[i][1], values[i]);
if(!graph.containsKey(equations[i][1])) graph.put(equations[i][1], new Node());
graph.get(equations[i][1]).nextNodes.put(equations[i][0], 1 / values[i]);
}
for(int i = 0; i < queries.length; i++){
if(!graph.containsKey(queries[i][0]) || !graph.containsKey(queries[i][1])) res[i] = -1.0;
else if(queries[i][0].equals(queries[i][1])) res[i] = 1.0;
else res[i] = dfs(queries[i][0], queries[i][1], graph);
for(String nd : graph.keySet()){
graph.get(nd).isVisit = false;
}
}
return res;
}
public double dfs(String start, String end, Map<String, Node> graph){
Stack<Node> stk = new Stack<Node>();
Stack<Double> valStk = new Stack<Double>();
stk.push(graph.get(start));
valStk.push(1.0);
while(!stk.isEmpty()){
Node nd = stk.pop();
double val = valStk.pop();
nd.isVisit = true;
for(String key : nd.nextNodes.keySet()){
if(key.equals(end)) return val *= nd.nextNodes.get(key);
else {
if(!graph.get(key).isVisit){
stk.push(graph.get(key));
valStk.push(val * nd.nextNodes.get(key));
}
}
}
}
return -1.0;
}
``````

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