题目：

给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例 :
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。

基于上述例子，输入如下：

equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-division
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答：

class Solution {
    public double[] calcEquation(List<List<String>> eq, double[] vals, List<List<String>> q) {
        Map<String,Map<String,Double>> m = new HashMap();
        //构建有向图
        for(int i=0;i<vals.length;i++){
            m.putIfAbsent(eq.get(i).get(0),new HashMap());
            m.putIfAbsent(eq.get(i).get(1),new HashMap());
            m.get(eq.get(i).get(0)).put(eq.get(i).get(1),vals[i]);
            m.get(eq.get(i).get(1)).put(eq.get(i).get(0),1/vals[i]);
        }
        double[] res = new double[q.size()];
        for(int i=0;i<q.size();i++){
            //深度优先遍历
            res[i] = dfs(q.get(i).get(0),q.get(i).get(1),1,m,new HashSet());
        }
        return res;
    }
    public double dfs(String s,String t,double r,Map<String, Map<String, Double>> m, Set<String> seen){
        if(!m.containsKey(s)||!seen.add(s))//add方法是为了避免重复而进入死循环
            return -1;
        if(s.equals(t))
            return r;
        Map<String, Double> next = m.get(s);
        for(String c:next.keySet()){
            double result = dfs(c,t,r*next.get(c),m,seen);
            if(result!=-1)
                return result;
        }
        return -1;
    }
}

看这题的时候可能一开始没想到是图，但开始写的时候就会发现这是个有向图，value就是每条边的权。

剩下的就是 dfs 了，没什么好解释的，看代码应该能看懂。