C++ DFS Solution


  • 0
    Y

    Building the graph and DFS the equation.

    class Solution {
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> query) {
            vector<double> ans(query.size());
            if(!query.size())
                return ans;
            unordered_map<string, unordered_map<string,double>> mp;
            unordered_set<string> vis;
            mp.clear();
            bool canReach = true;
            double res = 1.0, tmpres;
            for(int i = 0; i < equations.size(); ++ i){
                mp[equations[i].first][equations[i].second] = values[i];
                mp[equations[i].second][equations[i].first] = 1.0/values[i];
            }
            for(int i = 0; i < query.size(); ++ i){
                if(mp.find(query[i].first) == mp.end() || mp.find(query[i].second) == mp.end())
                    ans[i] = -1.0;
                else{
                    canReach = false;
                    tmpres = 1.0;
                    res = -1.0;
                    vis.clear();
                    vis.insert(query[i].first);
                    dfs(query[i].first, query[i].second, res, tmpres, canReach, mp, vis);
                    ans[i] = res;
                }
            }
            
            return ans;
        }
    private:
        void dfs(string &sta, string &ends, double &res, double &tmpres, bool &canReach, unordered_map<string, unordered_map<string,double>> &mp, unordered_set<string> &vis){
            if(sta == ends){
                res = tmpres;
                canReach = true;
                return ;
            }
            unordered_map<string,double>::iterator it = mp[sta].begin();
            double vres = 1.0;
            string u = "";
            for(; it != mp[sta].end(); ++ it){
                if(vis.find(it->first) != vis.end())
                    continue;
                vres = tmpres*it->second;
                u = it->first;
                vis.insert(it->first);
                dfs(u, ends, res, vres, canReach, mp, vis);
            }
        }
    };
    

  • 0
    C

    What's unordered_set<string> vis do here?


Log in to reply
 

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