# AC Java codes using graph idea

• ``````public class Solution {

private class Node{
String val;
public Node(String val){
this.val = val;
linkedNodes = new HashMap<Node, Double> ();
}

public void addNode(Node n, double w){
}
}

Map<String, Node> nodes;
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
nodes = new HashMap<String, Node>();
//Construct the graph
for (int i = 0; i < equations.length; i++){
Node A; Node B;
if (nodes.containsKey(equations[i][0])) A = nodes.get(equations[i][0]);
else { A = new Node(equations[i][0]); nodes.put(equations[i][0], A);}
if (nodes.containsKey(equations[i][1])) B = nodes.get(equations[i][1]);
else {B = new Node(equations[i][1]); nodes.put(equations[i][1], B);}
}
//Search in the graph
double[] res = new double[queries.length];
for (int i = 0; i < queries.length; i++){
if (!nodes.containsKey(queries[i][0]) || !nodes.containsKey(queries[i][1])) res[i] = -1;
else if (  queries[i][0].equals(queries[i][1]) ) res[i] = 1;
else{
Set<String> unVisited = new HashSet(nodes.keySet());
res[i] = bfs(nodes.get(queries[i][0]), queries[i][1], unVisited);
}
}
return res;
}

//May be actrually dfs
private double bfs(Node n, String target, Set<String> unVisited){
if (!unVisited.contains(n.val)) return -1;
else {
unVisited.remove(n.val);

for (Node subN: n.linkedNodes.keySet()){
if (subN.val.equals(target)) return n.linkedNodes.get(subN);
double res = bfs(subN, target, unVisited);
if (res != -1) return res*n.linkedNodes.get(subN);
}
return -1;
}
}
}

``````

• nice and clean code!

• Nice solution!

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