399. Evaluate Division

I don't have clue to solve the problem. I followed one of the top rated solutions.
The idea is that each equation is a link of graph with value as weight on the link. Note the graph should be directed because given a/b=x it's easy to get b/a=1/x. Therefore, for a query a/c, it is to find a valid path that connects node a and c.

For example, a / b = 3.0, b / c = 2.0, the graph looks like:
a <==> b <==> c. So for query, a/c, the path exists and the value is 3.0 * 2.0 = 6.0. On the other hand, for query c/a, the path also exists and the value is 1 / 3* 1 / 2 = 1 / 6.

The path can be find by DFS. Note, to avoid loop, i.e. a / b * b / a = 1, we need to have a set to cache the visited node.

1:  class Solution {  
2:  public:  
3:    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {  
4:      unordered_map<string, unordered_map<string, double>> mp;  
5:      for (int i = 0; i < equations.size(); i++) {  
6:        mp[equations[i].first].insert(make_pair(equations[i].second, values[i]));  
7:        mp[equations[i].second].insert(make_pair(equations[i].first, 1 / values[i]));  
8:      }  
9:      vector<double> res;  
10:      for (auto q : queries) {  
11:        unordered_set<string> s;  
12:        double tmp = check(mp, q.first, q.second, s);  
13:        if (tmp) res.push_back(tmp);  
14:        else res.push_back(-1);  
15:      }  
16:      return res;  
17:    }  
18:    double check(unordered_map<string, unordered_map<string, double>> &mp, string up, string down, unordered_set<string> &s) {  
19:      if (mp[up].find(down) != mp[up].end()) return mp[up][down];  
20:      for (auto it : mp[up]) {  
21:        if (s.find(it.first) == s.end()) {  
22:          s.insert(it.first);  
23:          double tmp = check(mp, it.first, down, s);  
24:          if (tmp) return it.second * tmp;  
25:        }  
26:      }  
27:      return 0;  
28:    }  
29:  };