# 0399. Evaluate Division
###### tags: `Leetcode` `Medium` `FaceBook` `BFS` `DFS` `Graph`
Link: https://leetcode.com/problems/evaluate-division/
## 思路 O(MN) O(N) M是query数量 N是equation数量
建图，然后DFS搜寻
**如果每走一步，都有值要更新，并且这个值与下面走到哪个node有关，就不要用iterative的方法做DFS，用recursive做backtracking**
**做backtracking的时候如果更改了前面某个变量的值，call function结束之后一定要复原**
例如：[0797. All Paths From Source to Target](https://hackmd.io/UkM9NX9GS_-cJpuOqcJCIA)
时间复杂度解释：For each query, we need to traverse the graph. In the worst case, we might need to traverse the entire graph, which could take O(N).
## Code

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        buildGraph(equations, values, graph);
        double[] res = new double[queries.size()];
        for(int i = 0;i < queries.size();i++){
            if(!graph.containsKey(queries.get(i).get(0)) || !graph.containsKey(queries.get(i).get(1))){
                res[i] = -1.0;
                continue;
            }
            Set<String> visited = new HashSet<>();
            res[i] = compute(graph, queries.get(i).get(0), queries.get(i).get(1), visited);
        }
        return res;
    }
    public void buildGraph(List<List<String>> equations, double[] values, Map<String, Map<String, Double>> graph){
        for(int i = 0;i < equations.size();i++){
            List<String> equation = equations.get(i);
            String u = equation.get(0);
            String v = equation.get(1);
            if(!graph.containsKey(u)) graph.put(u, new HashMap<String, Double>());
            if(!graph.containsKey(v)) graph.put(v, new HashMap<String, Double>());
            graph.get(u).put(v, values[i]);
            graph.get(v).put(u, 1/values[i]);
        }
    }
    public double compute(Map<String, Map<String, Double>> graph, String u, String v, Set<String> visited){
        visited.add(u);
        if(graph.get(u).containsKey(v)){
            return graph.get(u).get(v);
        }
        for(String next:graph.get(u).keySet()){
            if(!visited.contains(next)){
                double res = compute(graph, next, v, visited);
                if(res != -1){
                    return graph.get(u).get(next)*res;
                }
            }
        }
        return -1;
    }
}