399. Evaluate Division

bfs O(n) 有向图连通性

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for (int i = 0; i < equations.size(); ++i) {
            g[equations[i][0]][equations[i][1]] = values[i];
            g[equations[i][1]][equations[i][0]] = 1 / values[i];
        }
        vector<double> ret;
        for (auto&& query : queries) {
            ret.emplace_back(helper(query[0], query[1]));
        }
        return ret;
    }

    double helper(const string &begin, const string &end) {
        if (g.count(begin) == 0 || g.count(end) == 0) return -1.0;
        if (g.count(begin) && g[begin].count(end)) return g[begin][end]; // 假如cache里有则直接返回
        unordered_set<string> s; // 避免重复访问
        queue<pair<string, double>> q{{{begin, 1.0}}}; // key是点value是从begin到这个点的累乘结果，也就是begin / key的结果
        while (!q.empty()) {
            auto [u, product] = q.front(); q.pop();
            if (s.count(u)) continue;
            if (g[u].count(end)) return product * g[u][end];
            s.emplace(u);
            g[begin][u] = product; // cache中间结果
            g[u][begin] = 1 / product;
            for (auto [v, quotient] : g[u]) {
                q.emplace(v, product * quotient);
            }
        }
        return -1.0;
    }

    unordered_map<string, unordered_map<string, double>> g; // 这道题需要用邻接矩阵
};