[LeetCode]Evaluate Division

这个问题可以转化为有向图的问题，每一个equation(a / b = w)就是两条边，从a到b权重为w的边和从b到a的1/w的边。然后每一个query(a / b)就是寻找从a到b的一条path并把所有edge相乘，即使有很多path我么也只需要找到一条，因为只要input是自洽的那么每条path相乘的结果都是一样的，代码如下：

	class Solution {
	public:
	vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
	if(equations.size() != values.size())
	return {};
	int len = equations.size();
	unordered_map<string, vector<pair<string, double>>> g;
	for(int i = 0; i < len; ++i)
	{
	auto e = equations[i];
	double w = values[i];
	g[e.first].emplace_back(e.second, w);
	g[e.second].emplace_back(e.first, 1.0 / w);
	}
	vector<double> res;
	unordered_map<string, bool> visited;
	for(auto& q : queries)
	{
	double result = -1.0, curr = 1.0;
	query(g, visited, q.first, q.second, curr, result);
	res.emplace_back(result);
	}
	return res;
	}
	private:
	bool query(unordered_map<string, vector<pair<string, double>>>& g, unordered_map<string, bool>& visited, string curr, string target, double& val, double& res)
	{
	if(visited[curr] || g.find(curr) == g.end())
	return false;
	if(curr == target)
	{
	res = val;
	return true;
	}
	visited[curr] = true;
	bool find = false;
	for(auto& e : g[curr])
	{
	val *= e.second;
	if(query(g, visited, e.first, target, val, res))
	{
	find = true;
	break;
	}
	val /= e.second;
	}
	visited[curr] = false;
	return find;
	}
	};

view raw Evaluation division.cpp hosted with ❤ by GitHub