# C++ DFS solution

• firstly I defined one node to hold string and double value, like node. using the hash map to save all possible state transition. using the DFS algorithm to find the path from source to destination.

``````class Solution {
public:
struct node
{
string str;
double d;
node(string _str,double _d)
{
str = _str;d = _d;
}
};
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
unordered_map<string,vector<node>> map;
for(int i = 0;i<equations.size();i++)
{
string first = equations[i].first;
string second = equations[i].second;
map[first].push_back(node(second,values[i]));
map[second].push_back(node(first,1/values[i]));
}

vector<double>res;
for(auto query:queries)
{
string src = query.first;
string dst = query.second;
double result = 1.0;
unordered_set<string> set;
if(dfs(src,dst,map,set,result)) res.push_back(result);
else res.push_back(-1.0);
}
return res;
}
private:
bool dfs(string src,string dst,unordered_map<string,vector<node>>&map,unordered_set<string>&set,double &result)
{
if(map.find(src)==map.end()) return false; //make sure string is the dictionary
if(set.find(src)!=set.end()) return false; //visited before.
set.insert(src); //make source as visited
if(src.compare(dst)==0)return true; //found return

vector<node> next_string = map[src];
for(int i = 0;i<next_string.size();i++)
{
result = result*next_string[i].d;
if(dfs(next_string[i].str,dst,map,set,result)) return true;
result = result/next_string[i].d;
}
return false;
}
};
``````

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