c++ graph dfs solution


  • 0
    Q
    class Solution {
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            map<string,vector<string>> graph;
            map<string,vector<double>> weights;
            for(int i=0;i<equations.size();i++){
                string e1 = equations[i].first, e2 = equations[i].second;
                double w = values[i];
                graph[e1].push_back(e2);
                graph[e2].push_back(e1);
                weights[e1].push_back(w);
                weights[e2].push_back(1.0/w);
            }
            vector<double> res;
            for(auto it:queries){
                unordered_set<string> visited;
                string e1 = it.first, e2 = it.second;
                double re = dfs(graph,weights,e1,e2,1.0,visited);
                re = re == 0.0?-1.0:re;
                res.push_back(re);
            }
            return res;
        }
        double dfs(map<string,vector<string>> graph, map<string,vector<double>> weights, string start, string end, double res, unordered_set<string>& visited){
            if(visited.find(start) != visited.end() || graph.find(start) == graph.end())
                return 0.0;
            if(start == end)
                return res;
            visited.insert(start);
            double tmp = 0.0;
            for(int i=0;i<graph[start].size();i++){
                string e = graph[start][i];
                double w = weights[start][i];
                tmp = dfs(graph,weights,e,end,res*w,visited);
                if(tmp != 0.0)
                    return tmp;
            }
            visited.erase(start);
            return tmp;
        }
    };
    

Log in to reply
 

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