Concise 0ms C++ solution using Union-Find

• class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
for(int i=0;i<equations.size();i++){
string p = equations[i].first;
string q = equations[i].second;
if(id.find(p) == id.end())  id[p] = make_pair(p, 1);
if(id.find(q) == id.end())  id[q] = make_pair(q, 1);
unionFind(p, q, values[i]);
}

vector<double> res;
for(int i=0;i<queries.size();i++){
string p = queries[i].first;
string q = queries[i].second;
if(id.find(p) == id.end() || id.find(q) == id.end() || find(p).first != find(q).first)
res.push_back(-1);
else
res.push_back(find(p).second / find(q).second);
}
return res;
}

void unionFind(string p, string q, double v){
pair<string, double> proot = find(p);
pair<string, double> qroot = find(q);
id[proot.first].first = qroot.first;
id[proot.first].second = (v * qroot.second)/proot.second;
}

pair<string, double> find(string p){
double value = 1;
while(p != id[p].first){
id[p].second = id[p].second * id[id[p].first].second;
id[p].first  = id[id[p].first].first;
value = value * id[p].second;
p = id[p].first;
}
return make_pair(p, value);
}

private:
unordered_map <string, pair<string, double>> id;
};

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