# c++ BFS solution, easy to understand

• Build the graph first, then use BFS to get the value. I think the time complexity is O(N^2*query.size()), where N is the nodes number in the graph.

``````class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> query) {
unordered_map<string,unordered_map<string,double>> g;
for(int i=0;i<equations.size();i++){
g[equations[i].first].emplace(equations[i].second,values[i]);
g[equations[i].first].emplace(equations[i].first,1.0);
g[equations[i].second].emplace(equations[i].first,1.0/values[i]);
g[equations[i].second].emplace(equations[i].second,1.0);
}

vector<double> res;
for(auto item:query){
if(!g.count(item.first)||!g.count(item.second)) res.push_back(-1.0);
else{
queue<pair<string,double>> qs;
unordered_set<string> used;
qs.push({item.first,1.0});
used.insert(item.first);
bool find = false;
while(!qs.empty()&&!find){
queue<pair<string,double>> nex;
while(!qs.empty()&&!find){
pair<string,double> tp = qs.front();
qs.pop();

//check whether we find the divident
if(tp.first == item.second){
find = true;
res.push_back(tp.second);
break;
}

for(pair<string,double> values:g[tp.first]){
if(used.find(values.first) == used.end()){
values.second *= tp.second;
nex.push(values);
used.insert(values.first);
}
}
}

qs = nex;
}

if(!find) res.push_back(-1.0);
}
}

return res;
}
};
``````

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