C++, using UnionFind

• ``````class Solution {
private:
class UnionFind {
private:
unordered_map<string, pair<string, double>> roots;
unordered_map<string, unordered_set<string>> children;
public:
UnionFind(vector<pair<string, string>>& equations) {
for (auto& equation : equations) {
roots[equation.first] = {equation.first, 1};
roots[equation.second] = {equation.second, 1};
children[equation.first].insert(equation.first);
children[equation.second].insert(equation.second);
}
}
void unite(string a, string b, double val) {
if (roots[a].first == b || roots[b].first == a)
return;
if (roots[a].first != a || roots[b].first != b)
unite(roots[a].first, roots[b].first, roots[b].second * val / roots[a].second);
else {
if (children[a].size() < children[b].size()) {
swap(a, b);
val = 1 / val;
}
for (auto child : children[b]) {
children[a].insert(child);
roots[child] = {a, roots[child].second * 1 / val};
}
children[b].clear();
}
}
double find(string a, string b) {
if (roots.find(a) == roots.end() || roots.find(b) == roots.end())
return -1;
else if (roots[a].first == roots[b].first)
return roots[a].second / roots[b].second;
else if (roots[b].first == a)
return 1 / roots[b].second;
else if (roots[a].first == b)
return roots[a].second;
return -1;
}
};
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
UnionFind myFind(equations);
for (int i = 0; i < values.size(); i++)
myFind.unite(equations[i].first, equations[i].second, values[i]);
vector<double> ans;
for (auto& q : queries)
ans.push_back(myFind.find(q.first, q.second));
return ans;
}
};``````

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