# C++ 3ms solution using union-find

• ``````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;
}
}
}
};
``````

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