c++ BFS solution, easy to understand


  • 0
    W

    Build the graph first, then use BFS to get the value. I think the time complexity is O(N^2*query.size()), where N is the nodes number in the graph.

    class Solution {
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> query) {
            unordered_map<string,unordered_map<string,double>> g;
            for(int i=0;i<equations.size();i++){
                g[equations[i].first].emplace(equations[i].second,values[i]);
                g[equations[i].first].emplace(equations[i].first,1.0);
                g[equations[i].second].emplace(equations[i].first,1.0/values[i]);
                g[equations[i].second].emplace(equations[i].second,1.0);
            }
            
            vector<double> res;
            for(auto item:query){
                if(!g.count(item.first)||!g.count(item.second)) res.push_back(-1.0);
                else{
                    queue<pair<string,double>> qs;
                    unordered_set<string> used;
                    qs.push({item.first,1.0});
                    used.insert(item.first);
                    bool find = false;
                    while(!qs.empty()&&!find){
                        queue<pair<string,double>> nex;
                        while(!qs.empty()&&!find){
                            pair<string,double> tp = qs.front();
                            qs.pop();
                            
                            //check whether we find the divident
                            if(tp.first == item.second){
                                find = true;
                                res.push_back(tp.second);
                                break;
                            }
                            
                            for(pair<string,double> values:g[tp.first]){
                                if(used.find(values.first) == used.end()){
                                    values.second *= tp.second;
                                    nex.push(values);
                                    used.insert(values.first);
                                }
                            }
                        }
                        
                        qs = nex;
                    }
                    
                    if(!find) res.push_back(-1.0);
                }
            }
            
            return res;
        }
    };
    

Log in to reply
 

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