399. Evaluate Division

挺麻烦的，graph+dfs。归根结底还是在图中找路的问题。

class Solution { public: //start value:sum=1;visit[start]=1; bool findVal(int start,int end,vector<int>& visit,double& sum,vector<vector<double>>& result) { visit[start]=1; if(result[start][end]!=-1) { sum*=result[start][end]; return true; } else { for(int i=0;i<result.size();i++) { if(visit[i]==0&&result[start][i]!=-1) { sum*=result[start][i]; if(findVal(i,end,visit,sum,result)) return true; else sum/=result[start][i]; } } return false; } } vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) { map<string,int> func; int index=0; for(int i=0;i<equations.size();i++) { if(func.count(equations[i].first)==0) { func[equations[i].first]=index; index++; } if(func.count(equations[i].second)==0) { func[equations[i].second]=index; index++; } } vector<vector<double>> result; vector<double> temp(index,-1.0); for(int i=0;i<index;i++) result.push_back(temp); for(int i=0;i<index;i++) result[i][i]=1.0; for(int i=0;i<equations.size();i++) { int a=func[equations[i].first]; int b=func[equations[i].second]; result[a][b]=values[i]; result[b][a]=1/values[i]; } vector<double> res; for(int i=0;i<queries.size();i++) { if(func.count(queries[i].first)>0&&func.count(queries[i].second)>0) { int start=func[queries[i].first]; int end=func[queries[i].second]; double sum=1.0; vector<int> visit(index,0); if(findVal(start,end,visit,sum,result)) res.push_back(sum); else res.push_back(-1); } else res.push_back(-1); } return res; } };