import java.util.*;

public class evaluateDiv {

/*

Example:

Given a / b = 2.0, b / c = 3.0.

queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .

return [6.0, 0.5, -1.0, 1.0, -1.0 ].

equations = [ ["a", "b"], ["b", "c"] ],

values = [2.0, 3.0],

queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

* */

/*

有weight的有向图！

Image a/b = k as a link between node a and b, the weight from a to b is k, t

he reverse link is 1/k. Query is to find a path between two nodes.

* */

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

double[] res = new double[queries.length];

// build graph and edge weights

Map<String, ArrayList<String>> pairs = new HashMap<>();

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

for(int i = 0; i < equations.length; i++){

String[] equation = equations[i];

if(!pairs.containsKey(equation[0])){

pairs.put(equation[0], new ArrayList<>());

valuesPair.put(equation[0], new ArrayList<>());

}

if(!pairs.containsKey(equation[1])){

pairs.put(equation[1], new ArrayList<>());

valuesPair.put(equation[1], new ArrayList<>());

}

pairs.get(equation[0]).add(equation[1]);

pairs.get(equation[1]).add(equation[0]);

valuesPair.get(equation[0]).add(values[i]);

valuesPair.get(equation[1]).add(1/values[i]);

}

// for each query, use dfs to find path

for(int i = 0; i < queries.length; i++){

String[] query = queries[i];

res[i] = dfs(pairs,valuesPair,new HashSet<>(),query[0], query[1]);

if(res[i] == 0.0) res[i] = 1.0;

}

return res;

}

private double dfs(Map<String, ArrayList<String>> pairs, Map<String, ArrayList<Double>> valuesPair,

Set<String> visited, String start, String end){

// base cases

if(visited.contains(start)) return 0.0; // invalid circle in it

if(!pairs.keySet().contains(start) || !pairs.keySet().contains(end)) return 0.0;

if(start.equals(end)) return 1.0;

visited.add(start);

List<String> children = pairs.get(start);

List<Double> weights = valuesPair.get(start);

for(int i = 0; i < children.size(); i++){

double next = dfs(pairs, valuesPair,visited, children.get(i), end);

if(next != 0.0) return weights.get(i)*next;

}

visited.remove(start);

return 0.0;

}

}