[C++ Union Find Solution] O(n) for preprocessing, O(1) for each query


  • 0
    H
    class Solution {
    public:
        void merge (map<string, int> &groups, map<string, double> &weights, string a, string b, double value, int &index) {
            if (groups.find(a) == groups.end() && groups.find(b) == groups.end()) {
                groups[a] = index;
                groups[b] = index;
                ++index;
                
                weights[a] = value;
                weights[b] = 1.0;
            } else if (groups.find(a) != groups.end() && groups.find(b) == groups.end()) {
                groups[b] = groups[a];
                weights[b] = weights[a] / (value == 0.0 ? (1.0 / INT_MAX) : value);
            } else if (groups.find(a) == groups.end() && groups.find(b) != groups.end()) {
                groups[a] = groups[b];
                weights[a] = weights[b] * value;
            } else {
                if (groups[a] != groups[b]) {
                    int agroup = groups[a], bgroup = groups[b];
                    double ratio = weights[a] / ((weights[b] == 0.0 ? (1.0 / INT_MAX) : weights[b]) * value);
                    
                    for (auto mit = groups.begin(); mit != groups.end(); ++mit) {
                        if (mit->second == bgroup) {
                            groups[mit->first] = agroup;
                            weights[mit->first] = ratio * weights[mit->first];
                        }
                    }
                }
            }
        }
    
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, 
                                    vector<pair<string, string>> queries) {
            vector<double> res;
            int index = 0;
            map<string, int> groups;
            map<string, double> weights;
            
            for (int i = 0; i < equations.size(); ++i) 
                merge (groups, weights, equations[i].first, equations[i].second, values[i], index);
            for (pair<string, string> pit : queries) {
                string a = pit.first, b = pit.second;
                if (groups.find(a) == groups.end() || groups.find(b) == groups.end() || groups[a] != groups[b]) 
                    res.push_back(-1.0);
                else res.push_back(weights[a] / weights[b]);
            }
            return res;
        }
    };
    

Log in to reply
 

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