399. Evaluate Division

首先我們先紀錄一個string會對應到的string, 還有長度

像是

a -> b, length = 3

那反之

b -> a, length = 1/3

然後我們用dfs, 去尋找任意兩點間的距離, 如果Dfs走不出結果, 就回傳-1

class Solution {
public:
    double dfs(string a, string b, unordered_set<string> &visited){
        if(m[a].count(b)) return m[a][b];
        for(auto i: m[a]){
            if(visited.count(i.first)) continue;
            visited.insert(i.first);
            double t = dfs(i.first, b, visited);
            if(t > 0) return t * i.second;
        }
        return -1;
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        vector<double> res;
        for(int i = 0; i < equations.size();i++){
            m[equations[i][0]][equations[i][1]] = values[i];
            m[equations[i][1]][equations[i][0]] = 1 / values[i];
        }
        for(auto q: queries){
            unordered_set<string> visited;
            double t = dfs(q[0], q[1], visited);
            if(t > 0){
                res.push_back(t);
            }else{
                res.push_back(-1);
            }
        }
        return res;
    }
    unordered_map<string, unordered_map<string, double >> m;
};