CPP AC solution using graph


  • 0
    M
    double calcEquationdfs(unordered_map<string, vector<pair<string, double>>>& mp,
                         unordered_set<string>& vis, string start, string end, double res) {
      if (!mp.count(start) || !mp.count(end)) {
        return -1.0;
      }
      if (start == end) {
        return res;
      }
      
      for (auto n : mp[start]) {
        if (vis.count(n.first)) {
          continue;
        }
        vis.insert(n.first);
        double tmp;
        if ((tmp = calcEquationdfs(mp, vis, n.first, end, res * n.second)) != -1) {
          return tmp;
        }
        vis.erase(n.first);
      }
      
      return -1;
    }
    
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
      unordered_map<string, vector<pair<string, double>>> mp;
      vector<double> ans;
      int n = equations.size();
      
      for (int i = 0; i < n; i++) {
        mp[equations[i].first].
          push_back(make_pair(equations[i].second, values[i]));
        mp[equations[i].second].
          push_back(make_pair(equations[i].first, 1.0 / values[i]));
      }
      
      for (auto q : queries) {
        unordered_set<string> vis;
        vis.insert(q.first);
        ans.push_back(calcEquationdfs(mp, vis, q.first, q.second, 1.0));
      }
      
      return ans;
    }
    
    

Log in to reply
 

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