# c++ graph dfs solution

• ``````class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
map<string,vector<string>> graph;
map<string,vector<double>> weights;
for(int i=0;i<equations.size();i++){
string e1 = equations[i].first, e2 = equations[i].second;
double w = values[i];
graph[e1].push_back(e2);
graph[e2].push_back(e1);
weights[e1].push_back(w);
weights[e2].push_back(1.0/w);
}
vector<double> res;
for(auto it:queries){
unordered_set<string> visited;
string e1 = it.first, e2 = it.second;
double re = dfs(graph,weights,e1,e2,1.0,visited);
re = re == 0.0?-1.0:re;
res.push_back(re);
}
return res;
}
double dfs(map<string,vector<string>> graph, map<string,vector<double>> weights, string start, string end, double res, unordered_set<string>& visited){
if(visited.find(start) != visited.end() || graph.find(start) == graph.end())
return 0.0;
if(start == end)
return res;
visited.insert(start);
double tmp = 0.0;
for(int i=0;i<graph[start].size();i++){
string e = graph[start][i];
double w = weights[start][i];
tmp = dfs(graph,weights,e,end,res*w,visited);
if(tmp != 0.0)
return tmp;
}
visited.erase(start);
return tmp;
}
};
``````

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