unordered_map + DFS search


  • 0
    T
    class Solution {
    public:
        bool calc(double &fac, unordered_map<string, vector<pair<string,double>>>&graph, 
            unordered_set<string> &visited, string from, string to) {
            if (visited.find(from) != visited.end()) return false;
            if (from == to) return true;
            
            visited.insert(from);
            for (auto node:graph[from]) {
                fac *= node.second;
                if (calc(fac, graph, visited, node.first, to))
                    return true;
                fac /= node.second;
            }
            return false;
        }
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            unordered_map<string, vector<pair<string, double>>> graph;
            int sz = equations.size();
            for (int i = 0; i < sz; ++i) {
                graph[equations[i].first].emplace_back(equations[i].second, values[i]);
                graph[equations[i].second].emplace_back(equations[i].first, 1.0/values[i]);
            }
            vector<double>rst; rst.reserve(queries.size());
            for (auto q:queries) {
                unordered_set<string> visited1, visited2;
                double fac1 = 1.0, fac2 = 1.0;
                if (graph.find(q.first) != graph.end() && calc(fac1, graph, visited1, q.first, q.second))
                    rst.push_back(fac1);
                else if (graph.find(q.second) != graph.end() && calc(fac2, graph, visited2, q.second, q.first))
                    rst.push_back(1.0/fac2);
                else rst.push_back(-1.0);
            }
            return rst;
        }
    };
    

Log in to reply
 

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