# Straightforward C++ solution using hashmap and DFS, although a little long, 0ms

• ``````public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries){
unordered_map<string, int> vertex;
vector<vector<double>> edges;
buildgraph(vertex, edges, equations, values);
vector<double> result;
for(auto c: queries){
if(vertex.find(c.first) == vertex.end() || vertex.find(c.second) == vertex.end()){
result.push_back(-1.0);
continue;
}
bool flag = false;
vector<bool> used(vertex.size(), false);
double curresult = query(edges, vertex[c.first], vertex[c.second], 1.0, &flag, used);
if(flag){
result.push_back(curresult);
}
else{
result.push_back(-1);
}
}
return result;
}

void buildgraph(unordered_map<string, int> &vertex, vector<vector<double>> &edges, vector<pair<string, string>> &equations, vector<double>& values){
for(int i = 0, j = 0; j < equations.size(); j++){
if(vertex.find(equations[j].first) == vertex.end()){
vertex[equations[j].first] = i;i++;
}
if(vertex.find(equations[j].second) == vertex.end()){
vertex[equations[j].second] = i;i++;
}
}

edges.assign(vertex.size(), vector<double>(vertex.size(),-1.0));
for(int i = 0; i<vertex.size(); i++){
edges[i][i] = 1.0;
}
for(int j = 0; j<equations.size(); j++){
edges[vertex[equations[j].first]][vertex[equations[j].second]] = values[j];
edges[vertex[equations[j].second]][vertex[equations[j].first]] = 1.0/values[j];
}

return;
}

double query(vector<vector<double>> &edges, int first, int second, double value, bool *flag, vector<bool> &used){
if(first == second){
*flag = true;
return value;
}
used[first] = true;
for(int i = 0; i < edges.size(); i++){
if(!used[i] && edges[first][i] > 0){
value *= edges[first][i];
value = query(edges, i, second, value, flag, used);
if(*flag){
break;
}
value /= edges[first][i];
}
}
used[first] = false;
return value;
}
};``````

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