LeetCode 399. 除法求值

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_set<string> node;//记录所有节点
        unordered_map<string,unordered_map<string,double>> g;//存储图
        int n=equations.size(),m=queries.size();
        for(int i=0;i<n;i++)
        {
            string a=equations[i][0],b=equations[i][1];
            double c=values[i];
            //a->b的权值为c
            node.insert(a);node.insert(b);
            g[a][b]=c;g[b][a]=1/c;
        }
        vector<double> res;
        for(int i=0;i<m;i++)//处理询问
        {
            string a=queries[i][0],b=queries[i][1];
            if(node.find(a)==node.end()||node.find(b)==node.end())
                res.push_back(-1);
            else
            {
                double path=1;
                unordered_map<string,bool> st;
                st[a]=true;
                if(!dfs(a,b,g,path,st))   path=-1;
                res.push_back(path);
           }
        }
        return res;
    }
    bool dfs(string a,string b,unordered_map<string,unordered_map<string,double>> &g,double &sum,unordered_map<string,bool> &st)
    {
        if(a==b)    
            return true;
        for(auto item:g[a])
        {
            string t=item.first;
            if(!st[t])
            {
                st[t]=true;
                if(dfs(t,b,g,sum,st))
                {
                    sum*=item.second;
                    return true;
                }
            }
        }
        return false;
    }
};