# 0ms C++ graph and backtrace

• ``````struct Node {
string node;
double dist;
Node(string node_, double dist_) : node(node_), dist(dist_) {}
};
class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
//construct the map
unordered_map<string,vector<Node>> maps;
for(int i = 0 ;i < equations.size(); i++) {
Node n = Node(equations[i].second, values[i]);
Node m = Node(equations[i].first, 1/values[i]);
//   if (maps.find(equations[i].first) == maps.end())
//       maps[equations[i].first] = vector<Node>();
maps[equations[i].first].push_back(n);

//   if (maps.find(equations[i].second) == maps.end())
//       maps[equations[i].second] = vector<Node>();
maps[equations[i].second].push_back(m);
}

vector<double> ans;
for(int i = 0; i< queries.size(); i++) {
double res = 1.0;
set<string> path;
if(helper(res, maps, queries[i].first, queries[i].second, path))
ans.push_back(res);
else
ans.push_back(-1.0);
}
return ans;
}

bool helper(double& res, unordered_map<string,vector<Node>>& maps, string now, string dest, set<string>& path) {
if(maps.find(now) == maps.end() || path.find(now) != path.end()) return false;

if(now == dest)
return true;

path.insert(now);
for(auto k : maps[now]) {
res *= k.dist;
if (helper(res, maps, k.node, dest, path))
return true;
res /= k.dist;
}
path.erase(path.find(now));
return false;
}
};
``````

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