# Disgusting c++ solution

• Simple DFS solution using pair to keep precision as high as possible.
A/B saved as pair(A, B), Only divide at final step.

``````vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
unordered_map<pair<string, string>, pair<double, double>, string_pair_hash> expressions;
unordered_map<string, unordered_set<string>> pairs;
int size = equations.size();
for (int i = 0; i < size; i++) {
expressions[make_pair(equations[i].first, equations[i].second)] = make_pair(values[i], 1);
expressions[make_pair(equations[i].second, equations[i].first)] = make_pair(1, values[i]);
pairs[equations[i].first].insert(equations[i].second);
pairs[equations[i].second].insert(equations[i].first);
}
vector<double> results;
for (auto query : queries) {
unordered_set<string> accessed;
accessed.insert(query.first);
accessed.insert(query.second);
pair<double, double> result = calculate(expressions, query, pairs, accessed);
results.push_back(result.first == 0 && result.second == 0 ? -1.0 : result.first / result.second);
}
return results;
}

struct string_pair_hash {
std::size_t operator () (const pair<string, string> &p) const {
return p.first.size() ^ p.second.size();
}
};

pair<double, double> calculate(unordered_map<pair<string, string>, pair<double, double>, string_pair_hash> &expressions,
pair<string, string> p,
unordered_map<string, unordered_set<string>> &pairs,
unordered_set<string> &accessed) {
if (expressions.find(p) != expressions.end())
return expressions[p];
pair<double, double> result = make_pair(0.0, 0.0);
for (auto s : pairs[p.first]) {
if (accessed.find(s) == accessed.end()) {
accessed.insert(s);
pair<double, double> next = calculate(expressions, make_pair(s, p.second), pairs, accessed);
if (next.first != 0 || next.second != 0) {
pair<double, double> current = expressions[make_pair(p.first, s)];
result.first = current.first * next.first;
result.second = current.second * next.second;
break;
}
}
}
return result;
}
``````

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