C++, 0ms, graph dfs and union find solution


  • 0

    First DFS

    class Solution {
    private:
    unordered_map<string,unordered_map<string,double>> graph;
    unordered_set<string> zeros;
    
    public:
     bool dfs(double &res, string cur, string target, unordered_set<string> & visited){
         if (graph[cur].count(target)) {
             res*=graph[cur][target];
             return 1;
         }
         for (auto &x:graph[cur]){
             if (visited.count(x.first)) continue;
             res*=x.second;
             visited.insert(x.first);
             if (dfs(res,x.first,target,visited)) {
                 visited.erase(x.first);
                 return 1;
             }
             res/=x.second;
             visited.erase(x.first);
         }
         return false;
     }
    
     double getResult(pair<string,string> &x){
         if (graph.count(x.first)==0 || graph.count(x.second)==0) return -1;
         if (zeros.count(x.second)) return -1.0;
         if (zeros.count(x.first)) return 0;
         if (x.first==x.second) return 1.0;
         unordered_set<string> visited;
         double res=1.0;
         if (dfs(res,x.first,x.second,visited)) 
             return res;
         else
             return -1.0;
     }
    
    
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        vector<double> res;
        int sz = equations.size();
        for (int i=0;i<sz;i++){
            if  (values[i]==0) zeros.insert(equations[i].first);
            else{
                 graph[equations[i].first][equations[i].second]=values[i];
                 graph[equations[i].second][equations[i].first]=1.0/values[i];
            }
        }
        for (auto &x:queries){
            res.push_back(getResult(x));
        }
        return res;
    }
    };
    

    Then, union find. Obviously, union-find solution is much better for long queries

    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        
        unordered_map<string,pair<string,double>> graph;
        for (int i=0;i<equations.size();i++){
            pair<string,double> a,b;
            if (graph.count(equations[i].first) && graph.count(equations[i].second)){
                a = getParent(graph,equations[i].first);
                b = getParent(graph,equations[i].second);
                if (a.first==b.first) continue;
                else{
                    graph[a.first].first = b.first;
                    graph[a.first].second = 1/a.second*values[i]*b.second;
                }
            }else if(graph.count(equations[i].first)){
                a = getParent(graph,equations[i].first);
                graph[equations[i].second] = make_pair(a.first,1/values[i]*a.second);
            }else if(graph.count(equations[i].second)){
                b = getParent(graph,equations[i].second);
                graph[equations[i].first] = make_pair(b.first,values[i]*b.second);
            }else{
                graph[equations[i].first] = make_pair(equations[i].second,values[i]);
                graph[equations[i].second] = make_pair(equations[i].second,1);
            }
        }
        
        vector<double> res;
        for (auto &x:queries){
            if (!graph.count(x.first) || !graph.count(x.second)){
                res.push_back(-1.0);
            }else{
                pair<string,double> a,b;
                a = getParent(graph,x.first);
                b = getParent(graph,x.second);
                if (a.first!=b.first || b.second==0){
                    res.push_back(-1.0);
                }else{
                    res.push_back(a.second/b.second);
                }
            }
        }
        return res;
    }
    pair<string,double> getParent(unordered_map<string,pair<string,double>> &graph,string s){
        if (graph[s].first!=s){
            auto x=getParent(graph,graph[s].first);
            graph[s].first=x.first;
            graph[s].second*=x.second;
        }
        return graph[s];
    }

Log in to reply
 

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