力扣399【除法求值】【并查集】

• 思路
  1） 初始化映射，每个节点的父节点都是自己
  2） 根据输入的先验条件合并集合的union函数
  3）查找节点的父节点函数find,与此同时需要将树扁平化，改变搜索过程中经过的节点父节点为根节点，并更新权重
  
  这里使用递归进行查找
• code

    //寻找父亲根节点
    string find(string str)
    {
    
        if (MP1[str] != str)
        {
    
            string origin = MP1[str];
            MP1[str] = find(MP1[str]);
            MP2[str] *= MP2[origin];
        }
        return MP1[str];
    }

4. 判断两个节点是否在一个集合里，通过两个节点的根节点判断

• code

class Solution {
    
public:

    map<string, string> MP1;//记录节点的父亲根节点
    map<string, double> MP2;//记录节点的父节点到父亲节点的权重
    vector<double> res;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    

        //初始化map,自己是自己的根节点
        for (auto equation : equations)
        {
    
            for (auto str : equation)
            {
    
                MP1[str] = str;
                MP2[str] = 1.0;
            }
        }

        //合并根节点
        for (int i = 0; i < equations.size(); i++)
        {
    
            Union(equations[i][0],equations[i][1], values[i]);
        }

        
        for (int i = 0; i < queries.size(); i++)
        {
    
            string str1 = queries[i][0];
            string str2 = queries[i][1];
            if (is_set(str1, str2))
                res.push_back(MP2[str1] / MP2[str2]);
            else
                res.push_back(-1.0);
        }
        return res;
    }

    //合并
    void Union(string str1,string str2,double w)
    {
    
        string son = find(str1);
        string father = find(str2);
        if (father == son)
            return;
        MP1[son] = father;
        MP2[son] = w * MP2[str2] / MP2[str1];
    }

    //寻找父亲根节点
    string find(string str)
    {
    
        if (MP1[str] != str)
        {
    
            string origin = MP1[str];
            MP1[str] = find(MP1[str]);
            MP2[str] *= MP2[origin];
        }
        return MP1[str];
    }

    //判断是否在一个集合
    bool is_set(string str1, string str2)
    {
    
        if (MP1.find(str1) == MP1.end() || MP1.find(str2) == MP1.end())
        {
    
            return false;
        }
        if (find(str1) == find(str2))
            return true;
        return false;
    }
};

注意事项

我在写这道题的时候在这个地方犯了错