leetcode 399除法求值 超水带权并查集

题目

class Solution {
public:int f[45];double multi[45];map<string,int>hash;int tot=0;int seek(int x){if(x==f[x]) return x;int fa=f[x];f[x]=seek(fa);multi[x]*=multi[fa];return f[x];}vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {for(int i=0;i<equations.size();++i){vector<string> vec=equations[i];if(!hash.count(vec[0])) hash[vec[0]]=++tot,f[tot]=tot,multi[tot]=1.0;if(!hash.count(vec[1])) hash[vec[1]]=++tot,f[tot]=tot,multi[tot]=1.0;}for(int i=0;i<equations.size();++i){vector<string> vec=equations[i];int x=hash[vec[0]],y=hash[vec[1]];int rx=seek(x),ry=seek(y);if(rx==ry) continue;f[rx]=ry,multi[rx]=values[i]*multi[y]/multi[x];}vector<double>ans;for(int i=0;i<queries.size();++i){if(!hash.count(queries[i][0])||!hash.count(queries[i][1])) ans.push_back(-1);else{int x=hash[queries[i][0]],y=hash[queries[i][1]];int rx=seek(x),ry=seek(y);if(rx!=ry) ans.push_back(-1);else ans.push_back(multi[x]/(multi[y]*multi[rx]));}}return ans;}
};