unordered_map + DFS search

• ``````class Solution {
public:
bool calc(double &fac, unordered_map<string, vector<pair<string,double>>>&graph,
unordered_set<string> &visited, string from, string to) {
if (visited.find(from) != visited.end()) return false;
if (from == to) return true;

visited.insert(from);
for (auto node:graph[from]) {
fac *= node.second;
if (calc(fac, graph, visited, node.first, to))
return true;
fac /= node.second;
}
return false;
}
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
unordered_map<string, vector<pair<string, double>>> graph;
int sz = equations.size();
for (int i = 0; i < sz; ++i) {
graph[equations[i].first].emplace_back(equations[i].second, values[i]);
graph[equations[i].second].emplace_back(equations[i].first, 1.0/values[i]);
}
vector<double>rst; rst.reserve(queries.size());
for (auto q:queries) {
unordered_set<string> visited1, visited2;
double fac1 = 1.0, fac2 = 1.0;
if (graph.find(q.first) != graph.end() && calc(fac1, graph, visited1, q.first, q.second))
rst.push_back(fac1);
else if (graph.find(q.second) != graph.end() && calc(fac2, graph, visited2, q.second, q.first))
rst.push_back(1.0/fac2);
else rst.push_back(-1.0);
}
return rst;
}
};
``````

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