0ms C++ graph and backtrace


  • 0
    H
    struct Node {
      string node;
      double dist;
      Node(string node_, double dist_) : node(node_), dist(dist_) {} 
    };
    class Solution {
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
           //construct the map
           unordered_map<string,vector<Node>> maps;
           for(int i = 0 ;i < equations.size(); i++) {
               Node n = Node(equations[i].second, values[i]);
               Node m = Node(equations[i].first, 1/values[i]);
            //   if (maps.find(equations[i].first) == maps.end())
            //       maps[equations[i].first] = vector<Node>();
               maps[equations[i].first].push_back(n);
               
            //   if (maps.find(equations[i].second) == maps.end())
            //       maps[equations[i].second] = vector<Node>();
               maps[equations[i].second].push_back(m);
           }
           
           vector<double> ans;
           for(int i = 0; i< queries.size(); i++) {
               double res = 1.0;
               set<string> path;
               if(helper(res, maps, queries[i].first, queries[i].second, path))
                   ans.push_back(res);
               else
                   ans.push_back(-1.0);
           }
           return ans;
        }
        
        bool helper(double& res, unordered_map<string,vector<Node>>& maps, string now, string dest, set<string>& path) {
            if(maps.find(now) == maps.end() || path.find(now) != path.end()) return false;
            
            if(now == dest)
                return true;
            
            
            path.insert(now);
            for(auto k : maps[now]) {
                res *= k.dist;
                if (helper(res, maps, k.node, dest, path))
                    return true;
                res /= k.dist;
            }
            path.erase(path.find(now));
            return false;
        }
    };
    

Log in to reply
 

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