1、思路

• 用图来表示字符串之间的关系，比如{a, b}对应的值为2.0，那么可以想象成从a到b有一条路径，权值为2.0，同时能推导出从b到a也有一条路径，权值为0.5，这就是一张有向加权图；

• 用一张哈希表来存储这个图，hash的键表示起始节点from，值（也是一个哈希表）表示与起始节点邻接的所有节点to，值的键是to表示的字符串，值的值是从from到to的权值，即 $from \over to$ 的值；

• 题目所给数值均为正数，故可以用负数来表示不可达的情况；

• 若图中节点的数量为 $v$ ，边的数量为 $ee$ ，则时间复杂度为 $O(v + e)$。

2、代码

class Solution {
public:
    double dfs(unordered_map<string, unordered_map<string, double>>& hash, string from,
                string to, unordered_set<string>& visited)
    {
        if (from == to)
        {
            return 1.0;
        }

        visited.insert(from);
        for (auto &path : hash[from])       //遍历哈希表，注意此处 path 是一个 pair 形式的 HashMap
        {
            string toStr = path.first;      // to 代表的字符串
            double curVal = path.second;    //从 from 到 to 的值

            if (visited.find(toStr) == visited.end())
            {
                double nextVal = dfs(hash, toStr, to, visited);
                if (nextVal > 0)
                {
                    return curVal * nextVal;
                }
            }
        }

        visited.erase(from);
        return -1.0;                        //返回负数表示无可达路径
    }

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

        for (int i = 0; i < equations.size(); ++ i)                     //建图
        {
            hash[equations[i][0]][equations[i][1]] = values[i];         //从 from 到 to
            hash[equations[i][1]][equations[i][0]] = 1.0 / values[i];   //从 to 到 from
        }

        vector<double> res;

        for (int i = 0; i < queries.size(); ++ i)
        {
            string from = queries[i][0];
            string to = queries[i][1];

            if (hash.find(from) == hash.end() || hash.find(to) == hash.end())
            {
                res.push_back(-1);              //找不到终点或起点的情况，即不可达
            }
            else
            {
                unordered_set<string> visited;  //用一个哈希表记录走过的点
                res.push_back(dfs(hash, from, to ,visited));
            }
        }

        return res;
    }
};