C++ dfs solution


  • 1
    J
    class Solution {
    public:
    	bool dfs(unordered_map<string, vector<pair<string, double>>>& g, unordered_set<string>& visited, string& s, string& e, double& res) {
    		if (g.count(s) == 0) return false;
    		if (s == e) return true;
    
    		for (int i = 0; i < g[s].size(); i++) {
    			if (visited.count(g[s][i].first) == 0) {
    				visited.insert(g[s][i].first);
    				double old = res;
    				res *= g[s][i].second;
    				if (dfs(g, visited, g[s][i].first, e, res))
    					return true;
    				res = old;
    				visited.erase(g[s][i].first);
    			}
    		}
    
    		return false;
    	}
    
    	vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> query) {
    		unordered_map<string, vector<pair<string, double>>> g;
    		vector<double> result;
    
    		for (int i = 0; i < equations.size(); i++) {
    			g[equations[i].first].push_back(make_pair(equations[i].second, values[i]));
    			g[equations[i].second].push_back(make_pair(equations[i].first, double(1.0f/values[i])));
    		}
    
    		for (int i = 0; i < query.size(); i++) {
    			unordered_set<string> visited;
    			visited.insert(query[i].first);
    			double res = 1;
    			if(dfs(g, visited, query[i].first, query[i].second, res))
    				result.push_back(res);
    			else
    				result.push_back(-1);
    		}
    
    		return result;
    	}
    };
    

Log in to reply
 

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