399. Evaluate Division ---------------H ~~~~~~~~！！！！

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

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

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

 

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
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 ]
note: x is undefined => -1.0

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

 

Constraints:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj consist of lower case English letters and digits.

A:

build a graph， then do dfs to find the path from C to D.

class Solution {

public:

vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {

// build a graph, so that we can reach C to D at query

// find nodes

unordered_set<string> S;

for(auto eq : equations){

S.insert(eq[0]);

S.insert(eq[1]);

}

vector<double> results;

for(auto & query : queries){

string C = query[0], D = query[1];

if(S.find(C) == S.end() || S.find(D) == S.end()){

results.emplace_back(-1);

continue;

}

unordered_set<string> visited;

double res;

if(dfs(equations, values, visited, C,D, res))

results.emplace_back(res);

else

results.emplace_back(-1);

}

return results;

}

private:

bool dfs(vector<vector<string>>& equations, vector<double>& values, unordered_set<string> &visited, string C, string D, double &res){

if(visited.find(C) != visited.end()){ // if already visited.

return false;

}

if(C==D){

res = 1;

return true;

}

visited.insert(C);

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

string A = equations[i][0], B = equations[i][1];

if(C == A){

auto tmp = dfs(equations, values, visited, B, D, res);

if(tmp){

res = values[i] * res;

return true;

}

}else if(C == B){

auto tmp = dfs(equations, values, visited, A, D, res);

if(tmp){

res = res / values[i];

return true;

}

}

}

visited.erase(C);

return false;

}

};

上面解法的弱点（不好看的点）就是需要检查C/D是否已经被发现。否则不容易分辨检查二者是否相等的情况

主要思路，就是递归找关系， 并把其结果乘积。下面的方法，并没有考虑 e /a. = 1, e/b = 1. 然后求a/b的。 所以时错误的

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        vector<double> res;
        int N = equations.size();
        unordered_map<string, unordered_map<string, double>> map;
        for(int i =0;i<N;i++){
            string dividend = equations[i][0];
            string divisor =  equations[i][1];
            // include themselves
            map[dividend][dividend] = 1;
            map[divisor][divisor] = 1;
                       
            double value = values[i];
            map[dividend][divisor] = value;
            if(value != 0 ) // as equations can exist 0 / a = 0
                map[divisor][dividend] = 1.0 / value;
        }
        unordered_set<string> usedStrings;
        for(auto query : queries){
            res.push_back(dfs(query[0], query[1], map, usedStrings));
        }
        return res;
    }
private:
    double dfs(string a, string b, unordered_map<string, unordered_map<string, double>> &map, unordered_set<string> &usedStrings){
        if(usedStrings.find(a) != usedStrings.end()){
            return -1;
        }
        if(map[a].find(b) != map[a].end()){
            return map[a][b];
        }else{
            usedStrings.insert(a);
            double res = -1;
            auto iter = map[a].begin();
            while(iter!= map[a].end()){
                res = (iter->second) * dfs(iter->first, b, map, usedStrings);
                if(res != -1){
                    break;
                }
                iter++;
            }
            usedStrings.erase(a);
            return res;
        }
    }
};

Errors:

1:  map里由于我保存了 a->b    b -> a 这样会造成循环

2: 再就是double 给写成 long,  肏

----------第二遍----------- DFS。   每次只考虑  A >= B 的情况， 否则就inverse ---

但这样是不行的。 比如 e=2a, e = 3b

我们插入的就只有上面的。 query时，  无法倒回来通过e的关系

NOTE

     因为dfs的时候， 可能-1是来自于 不存在。 也可能是来自于正常的计算结果。 因此不能仅仅靠返回一个double值。 而是要返回bool,  结果保存在另一个参数里