399. Evaluate Division ---------------M ~~~~~~~~！！！！

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

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 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<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. 

A:

再一次，VS上的结果是对的。LC结果不对。 哎。不管了

主要思路，就是递归找关系， 并把其结果乘积。

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,  肏