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;
    }
};