Union-Find && C++


  • 0
    Y
    class Solution {
    public:
        unordered_map<string,pair<string,double>> m;
        vector<double> calcEquation(vector<pair<string, string>> equations, 
                        vector<double>& values, vector<pair<string, string>> queries) {
            int N = equations.size(), M = queries.size();
            for(int i = 0; i < N; i++){
                m[equations[i].first] = make_pair(equations[i].first, 1.0);
                m[equations[i].second] = make_pair(equations[i].second, 1.0);
            }
            for(int i = 0; i < N; i++){
                combine(equations[i].first, equations[i].second, values[i]);     
            }
            vector<double> ret;
            for(int i = 0; i < M; i++){
                if(!m.count(queries[i].first) || !m.count(queries[i].first))
                    ret.push_back(-1.0);
                else{
                    pair<string,double>  a = find(queries[i].first);
                    pair<string,double>  b = find(queries[i].second);
                    ret.push_back(a.first == b.first && a.second != 0 ? b.second / a.second : -1.0);
                }
            }   
            return ret;
        }
    
        pair<string,double> find(string str){
            string var = str;
            double ret = 1.0;
            while(m[var].first != var){
                cout << var << m[var].second << endl;
                ret *= m[var].second;
                var = m[var].first;
            }
            // cout << "var: " << var << " ret: " << ret << endl;
            return make_pair(var,ret);
        }
    
        void combine(string& var1, string& var2, double value){
            pair<string,double> root1 = find(var1);
            pair<string,double> root2 = find(var2);
            // cout << "var1: " << var1 << " var2: " << var2 << " value: " << value << endl;;
            m[root2.first].first = root1.first;
            m[root2.first].second = value * root1.second / root2.second;
            // cout << root2.first << " " << m[root2.first].second << endl;
        }
    };
    

Log in to reply
 

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