399. Evaluate Division

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.

• new solution update 2022.02.09

class Solution {
    unordered_map<string, string> group;
    unordered_map<string, vector<pair<string, double>>> graph;
    unordered_map<string, double> dp;
    string find(string& str) {
        return group[str] == str ? str : group[str] = find(group[str]);
    }
    void merge(string& a, string& b) {
        string pa = find(a);
        string pb = find(b);
        group[pa] = group[pb] = min(pa,pb);
    }
    bool eqGroup(string& a, string& b) {
        return group.count(a) && group.count(b) && (find(a) == find(b));
    }
    double bfs(string& from, string& to) {
        string key = from + "#" + to;
        if(dp.count(key)) return dp[key];

        queue<pair<string, double>> q;
        unordered_set<string> visit;
        q.push({from, 1.0});
        visit.insert(from);

        while(!q.empty()) {
            auto [str, val] = q.front(); q.pop();
            for(auto [nxt, cost] : graph[str]) {
                if(visit.count(nxt)) continue;
                double nxtVal = cost * val;
                q.push({nxt, nxtVal});
                visit.insert(nxt);
                dp[from + "#" + nxt] = nxtVal;
            }
        }

        return dp[key];
    }
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for(int i = 0; i < equations.size(); i++) {
            if(!group.count(equations[i][0])) group[equations[i][0]] = equations[i][0];
            if(!group.count(equations[i][1])) group[equations[i][1]] = equations[i][1];
            merge(equations[i][0],equations[i][1]);
            graph[equations[i][0]].push_back({equations[i][1], values[i]});
            graph[equations[i][1]].push_back({equations[i][0], 1/values[i]});
        }
        vector<double> res;
        for(auto& q : queries) {
            if(eqGroup(q[0],q[1])) {
                if(q[0] == q[1]) res.push_back(1.0);
                else res.push_back(bfs(q[0],q[1]));
            } else res.push_back(-1.0);
        }
        return res;
    }
};

class Solution {
    double bfs(string from, string to, unordered_map<string, list<pair<string, double>>>& m) {
        unordered_set<string> v;
        queue<pair<string, double>> q;
        q.push({from, 1.0});
        v.insert(from);
        while(!q.empty()) {
            auto p = q.front();
            q.pop();
            for(auto& near : m[p.first]) {
                if(near.first == to) return p.second * near.second;
                if(v.count(near.first)) continue;
                v.insert(near.first);
                q.push({near.first, p.second * near.second});
            }
        }
        return -1.0;
    }
public:
    vector<double> calcEquation(vector<vector<string>>& e, vector<double>& v, vector<vector<string>>& q) {
        unordered_map<string, list<pair<string, double>>> m;
        vector<double> res;
        for(int i = 0; i < v.size(); i++) {
            m[e[i].front()].push_back({e[i].back(), v[i]});
            m[e[i].back()].push_back({e[i].front(), 1/v[i]});
        }
        for(auto& query : q) {
            res.push_back(bfs(query.front(), query.back(), m));
        }
        return res;
    }
};