C++ disjoint set 0ms


  • 0
    B

    for each set, each element has a reference value to its parent

    for the query, we can get a value if both element are in the same set, otherwise it is -1.0

    for performance, the operation in disjoint set are amortized O(1), so the overall performance is O(m+n), where m is the input condition, and n is the size of queries

    class Solution {
    public:
        string getParent(unordered_map<string,string> & parent, unordered_map<string, double> & val, string s)
        {
            if(parent[s] == s) return s;
            string s1 = getParent(parent, val, parent[s]);
            if(s1 == parent[s]) return s1;
            val[s] *= val[parent[s]];
            parent[s] = s1;
            return parent[s];
        }
    
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            unordered_map<string,string>parent;
            unordered_map<string, double>val;
            for(int i = 0; i < equations.size(); i++)
            {
                string s1 = equations[i].first;
                string s2 = equations[i].second;
                if(parent.find(s1)==parent.end() && parent.find(s2)==parent.end())
                {
                    parent[s1] = s2;
                    parent[s2] = s2;
                    val[s2] = 1;
                    val[s1] = values[i];
                }
                else if(parent.find(s1) == parent.end())
                {
                    string s = getParent(parent, val, s2);
                    double v1 = val[s2]*values[i];
                    if(s != s2) v1 *= val[s];
                    if(v1 > 1)
                    {
                        parent[s1] = s;
                        val[s1] = v1;
                    }
                    else
                    {
                        parent[s] = s1;
                        parent[s1] = s1;
                        val[s1] = 1;
                        val[s] = 1/v1;
                    }
                }
                else if(parent.find(s2) == parent.end())
                {
                    string s = getParent(parent, val, s1);
                    double v2 = val[s1]/values[i];
                    if(s != s1) v2 *= val[s];
                    if(v2 > 1)
                    {
                        parent[s2] = s;
                        val[s2] = v2;
                    }
                    else
                    {
                        parent[s] = s2;
                        parent[s2] = s2;
                        val[s2] = 1;
                        val[s] = 1/v2;
                    }
                }
                else
                {
                    string str1 = getParent(parent, val, s1);
                    string str2 = getParent(parent, val, s2);
                    if(str1 != str2)
                    {
                        double v = val[s2] * values[i] / val[s1];
                        if(v>1)
                        {
                            parent[str1] = str2;
                            val[str1] = val[str2] * v;
                        }
                        else
                        {
                            parent[str2] = str1;
                            val[str2] = val[str1] / v;
                        }
                    }
                }
            }
            
            vector<double>ans;
            for(auto e : queries)
            {
                if(parent.find(e.first) == parent.end() || parent.find(e.second) == parent.end())
                {
                    ans.push_back(-1.0);
                    continue;
                }
                string str1 = getParent(parent, val, e.first);
                string str2 = getParent(parent, val, e.second);
                if(str1 == str2) ans.push_back(val[e.first] / val[e.second]);
                else ans.push_back(-1.0);
            }
            return ans;
        }
    };

  • 0

    Why are the operations in disjoint set amortized O(1)?


  • 0
    B

    @hwf the only cost that greater than O(1) is recursively find parent. All elements along the path from one element to the head of this set would directly connect to the head, so that future query to find parent would be O(1), so it is amortized O(1).

    My wording may not be good to understand, you can refer to some tutorial about dis-joint set / union-find data structure.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.