Equations are given in the formatA / B = k, whereAandBare variables represented as strings, andkis a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return-1.0.

Example:
Givena / 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 ].

The input is:vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries, whereequations.size() == values.size(), and the values are positive. This represents the equations. Returnvector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

tag: BFS, DFS

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, List<String>> pairs = new HashMap<>();
        Map<String, List<Double>> pairValues = 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<String>());
                pairValues.put(equation[0], new ArrayList<Double>());
            }
            if (!pairs.containsKey(equation[1])){
                pairs.put(equation[1], new ArrayList<String>());
                pairValues.put(equation[1], new ArrayList<Double>());
            }

            pairs.get(equation[0]).add(equation[1]);
            pairValues.get(equation[0]).add(values[i]);
            pairs.get(equation[1]).add(equation[0]);
            pairValues.get(equation[1]).add(1.0 / values[i]);
        }

        double[] ans = new double[queries.length];
        for (int i = 0; i < queries.length; i++){
            String[] query = queries[i];
            ans[i] = dfs(query[0], query[1], pairs, pairValues, new HashSet<String>(), 1.0);
            if (ans[i] == 0) ans[i] = -1.0;
        }

        return ans;
    }

    private double dfs(String start, String end, Map<String, List<String>> pairs, Map<String, List<Double>> pairValues, Set<String> set, double value){
        if (!pairs.containsKey(start)) return 0.0;
        if (set.contains(start)) return 0.0;
        if (start.equals(end)) return value;

        set.add(start);

        List<String> pairList = pairs.get(start);
        List<Double> valueList = pairValues.get(start);
        double temp = 0.0;
        for (int i = 0; i < pairList.size(); i++){
            temp = dfs(pairList.get(i), end, pairs, pairValues, set, value * valueList.get(i));
            if (temp != 0.0) break;
        }
        set.remove(start);
        return temp;
    }
}