题目链接
思路：
建立图结构，（节点可以用自定义结构体或类，也可以用容器配合pair）被除数/除数作为节点，之间的商作为节点间的权重值。
转换成图后，题目可以转换为求两点间的权重值。因为不需要寻求最短路径，所以dfs和bfs都可，这里使用dfs。
class Solution
{
public:unordered_map<string, vector<pair<string, double>>> mGraph;vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values, vector<vector<string>> &queries){
vector<double> res;// 建立图for (int i = 0; i < equations.size(); i++){
mGraph[equations[i][0]].push_back({
equations[i][1], values[i]});mGraph[equations[i][1]].push_back({
equations[i][0], 1 / values[i]});}// 求结果for (int i = 0; i < queries.size(); i++){
res.push_back(dfs(queries[i][0], queries[i][1]));}return res;}double dfs(const string &src, const string &des){
if (!mGraph.count(src) || !mGraph.count(des)){
return -1.0;}if (src == des){
return 1.0;}queue<pair<string, double>> que;unordered_set<string> visited;que.push({
src, 1.0});while (!que.empty()){
pair<string, double> mSrcVal = que.front();que.pop();if (mSrcVal.first == des){
return mSrcVal.second;}visited.insert(mSrcVal.first);for (auto vec : mGraph[mSrcVal.first]){
if (!visited.count(vec.first)){
que.push({
vec.first, vec.second * mSrcVal.second});}}}return -1;}
};