# 4 ms java O(v+e+n) solution

• DFS on all connected component of the graph, use the root of the dfs spinning tree as an intermediate node when calculating the ratio between two nodes. correct me if I'm wrong about the time complexity. n: the number of queries.

``````    class Node{
String name;
List<Node> adjs = new ArrayList<>();
List<Double> adjsDiv = new ArrayList<>();
Node root;//root in the search spinning tree
double divRoot = 0.0; // ?
public Node(String name){
this.name = name;
}
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
int n = equations.length;
int m = queries.length;
HashMap<String, Node> graph = new HashMap<>();
for(int i=0; i<n; i++){
String uName = equations[i][0];
String vName = equations[i][1];
double uDevideV = values[i];
Node uNode = graph.get(uName);
if(uNode == null){
uNode = new Node(uName);
graph.put(uName, uNode);
}
Node vNode = graph.get(vName);
if(vNode == null){
vNode = new Node(vName);
graph.put(vName, vNode);
}
}
HashSet<Node> visited = new HashSet<>();
for(Node node : graph.values()){
dfs(1.0, node, node, graph, visited);
}
double[] ans = new double[m];
for(int i=0; i<m; i++){
String u = queries[i][0];
String v = queries[i][1];
Node uNode = graph.get(u);
Node vNode = graph.get(v);
if(uNode == null || vNode == null || uNode.root != vNode.root){
ans[i] = -1.0;
continue;
}
ans[i] = uNode.divRoot/vNode.divRoot;
}
return ans;
}

private void dfs(double rootDiv, Node root, Node curr, HashMap<String, Node> graph, HashSet<Node> visited){
if(visited.contains(curr)) return;
curr.root = root;
curr.divRoot = 1.0/rootDiv;