C++ 0ms 23 lines DFS solution with comments

• ``````class Solution {
private:
unordered_map<string, vector<pair<string, double>>> children;                               // adjacency list

pair<bool, double> search(string& a, string& b, unordered_set<string>& visited, double val) {
if (visited.count(a) == 0) {
visited.insert(a);                                                                  // mark a as visited
for (auto p : children[a]) {
double temp = val * p.second;                                                   // potential result
if (p.first == b) { return make_pair(true, temp); }                             // found result

auto result = search(p.first, b, visited, temp);
if (result.first) { return result; }
}
}
return make_pair(false, -1.0);
}

public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
vector<double> ans;

for (int i = 0; i < equations.size(); i++) {
children[equations[i].first].push_back(make_pair(equations[i].second, values[i]));      // build graph list a->b
children[equations[i].second].push_back(make_pair(equations[i].first, 1.0 / values[i]));// build graph list b->a
}

for (auto p : queries) {
unordered_set<string> visited;                                                          // to record visited nodes
// p.first == p.second is special case
ans.push_back(p.first == p.second && children.count(p.first) ? 1.0 : search(p.first, p.second, visited, 1.0).second);
}

return ans;
}
};
``````

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