0ms cpp solution using bfs


  • 0
    T
     unordered_map<string, double> BFSEqls(int i, vector<int> &visited, const vector<pair<string, string>> &equations, vector<double>& values){
            const int &EN = equations.size();
            unordered_map<string, double> res;
            deque<int> que;
            que.push_back(i);
            visited[i] = 1;
            while(!que.empty()){
                auto curi = que.front(); que.pop_front();
                if(res.empty()){
                    if(fabs(values[curi]) >= 1e-9)
                        res[equations[curi].second] = 1.0;
                    res[equations[curi].first] = values[curi];
                }else{
                    if(res.find(equations[curi].first) == res.end())
                        res[equations[curi].first] = res[equations[curi].second] * values[curi];
                    else if(fabs(values[curi]) >= 1e-9){
                        res[equations[curi].second] = res[equations[curi].first] / values[curi];
                    }
                }
                for(int j = i+1; j < EN; ++j){
                    if(visited[j] != 0) continue;
                    bool notfound1 = res.find(equations[j].first) == res.end();
                    bool notfound2 = res.find(equations[j].second) == res.end();
                    if(notfound1 && notfound2) continue;
                    if(!notfound1 && !notfound2) continue;
                    que.push_back(j);
                    visited[j] = 1;
                }
            }
            return res;
        }
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            const int EN = equations.size();
            vector<int> visited(EN, 0);
            vector<unordered_map<string, double>> groups;
            unordered_map<string, int> strToGroupi;
            for(int i = 0; i < EN; ++i){
                if(0 == visited[i]){
                    auto strval = BFSEqls(i, visited, equations, values);
                    for(auto apair:strval) strToGroupi[apair.first] = groups.size();
                    groups.emplace_back(strval);
                }
            }
            const int QN = queries.size();
            vector<double> res(QN, -1.0);
            for(int i = 0; i < QN; ++i){
                if(strToGroupi.find(queries[i].first) == strToGroupi.end()) continue;
                if(strToGroupi.find(queries[i].second) == strToGroupi.end()) continue;
                int gi = strToGroupi[queries[i].first];
                if(strToGroupi[queries[i].second] != gi) continue;
                double secondval = groups[gi][queries[i].second];
                if(fabs(secondval) < 1e-9) continue;
                res[i] = groups[gi][queries[i].first] / secondval;
            }
            return res;
        }

Log in to reply
 

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