Li Kou 399 [division evaluation] [joint query]

• Ideas
  1） Initialize mapping , The parent node of each node is itself
  2） Merges sets of according to the entered prior conditions union function
  3） Find the parent node function of the node find, At the same time, we need to flatten the tree , Change the parent node of the node passed in the search process to the root node , And update the weight
  
  Here we use recursion to find
• code

    // Find parent root node 
    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. Determine whether two nodes are in a set , Judge by the root node of the two nodes

• code

class Solution {
    
public:

    map<string, string> MP1;// Record the parent root node of the node 
    map<string, double> MP2;// Record the weight from the parent node to the parent node 
    vector<double> res;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    

        // initialization map, You are your own root node 
        for (auto equation : equations)
        {
    
            for (auto str : equation)
            {
    
                MP1[str] = str;
                MP2[str] = 1.0;
            }
        }

        // Merge the root node 
        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;
    }

    // Merge 
    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];
    }

    // Find parent root node 
    string find(string str)
    {
    
        if (MP1[str] != str)
        {
    
            string origin = MP1[str];
            MP1[str] = find(MP1[str]);
            MP2[str] *= MP2[origin];
        }
        return MP1[str];
    }

    // Determine whether it is in a set 
    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;
    }
};

matters needing attention

I made a mistake in this place when I was writing this question