C++ 3ms solution using union-find


  • 0
    H
    class Solution {
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            int n = 0;
            for(int i = 0; i < equations.size(); i++){
                if(map1.count(equations[i].first) == 0){
                    map1[equations[i].first] = n++;
                }
                if(map1.count(equations[i].second) == 0){
                    map1[equations[i].second] = n++;
                }
            } 
            
            vector<pair<int, double>> parent(n, {-1, 1.0});
            for(int i = 0; i < parent.size(); i++) parent[i].first = i;
            for(int i = 0; i < equations.size(); i++){
                int idx1 = map1[equations[i].first];
                int idx2 = map1[equations[i].second];
                int p1 = findAncestor(parent, idx1);
                int p2 = findAncestor(parent, idx2);
                if(p1 == p2) continue;
                else{
                    double ratio = parent[idx2].second*values[i]/parent[idx1].second;
                    unionAncestor(parent, p1, p2, ratio);
                }
            }
            
            vector<double> res;
            for(auto q:queries){
                if(!map1.count(q.first) || !map1.count(q.second)){
                    res.push_back(-1);
                    continue;
                }
                int p1 = findAncestor(parent, map1[q.first]);
                int p2 = findAncestor(parent, map1[q.second]);
                if(p1 != p2) res.push_back(-1);
                else{
                    res.push_back(parent[map1[q.first]].second/parent[map1[q.second]].second);
                }
            }
            
            return res;
        }
    private:
        unordered_map<string, int> map1;
        int findAncestor(vector<pair<int, double>>& parent, int i){
            while(parent[i].first != i){
                i = parent[i].first;
            }
            return i;
        }
        
        void unionAncestor(vector<pair<int, double>>& parent, int p1, int p2, double ratio){
            for(auto& p:parent){
                if(p.first == p1){
                    p.second *= ratio;
                    p.first = p2;
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.