# C++ dfs solution

• ``````class Solution {
public:
bool dfs(unordered_map<string, vector<pair<string, double>>>& g, unordered_set<string>& visited, string& s, string& e, double& res) {
if (g.count(s) == 0) return false;
if (s == e) return true;

for (int i = 0; i < g[s].size(); i++) {
if (visited.count(g[s][i].first) == 0) {
visited.insert(g[s][i].first);
double old = res;
res *= g[s][i].second;
if (dfs(g, visited, g[s][i].first, e, res))
return true;
res = old;
visited.erase(g[s][i].first);
}
}

return false;
}

vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> query) {
unordered_map<string, vector<pair<string, double>>> g;
vector<double> result;

for (int i = 0; i < equations.size(); i++) {
g[equations[i].first].push_back(make_pair(equations[i].second, values[i]));
g[equations[i].second].push_back(make_pair(equations[i].first, double(1.0f/values[i])));
}

for (int i = 0; i < query.size(); i++) {
unordered_set<string> visited;
visited.insert(query[i].first);
double res = 1;
if(dfs(g, visited, query[i].first, query[i].second, res))
result.push_back(res);
else
result.push_back(-1);
}

return result;
}
};
``````

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