C++, using UnionFind


  • 0
    O
    class Solution {
    private:
        class UnionFind {
        private:
            unordered_map<string, pair<string, double>> roots;
            unordered_map<string, unordered_set<string>> children;
        public:
            UnionFind(vector<pair<string, string>>& equations) {
                for (auto& equation : equations) {
                    roots[equation.first] = {equation.first, 1};
                    roots[equation.second] = {equation.second, 1};
                    children[equation.first].insert(equation.first);
                    children[equation.second].insert(equation.second);
                }
            }
            void unite(string a, string b, double val) {
                if (roots[a].first == b || roots[b].first == a)
                    return;
                if (roots[a].first != a || roots[b].first != b)
                    unite(roots[a].first, roots[b].first, roots[b].second * val / roots[a].second);
                else {
                    if (children[a].size() < children[b].size()) {
                        swap(a, b);
                        val = 1 / val;
                    }
                    for (auto child : children[b]) {
                        children[a].insert(child);
                        roots[child] = {a, roots[child].second * 1 / val};
                    }
                    children[b].clear();
                }
            }
            double find(string a, string b) {
                if (roots.find(a) == roots.end() || roots.find(b) == roots.end())
                    return -1;
                else if (roots[a].first == roots[b].first)
                    return roots[a].second / roots[b].second;
                else if (roots[b].first == a)
                    return 1 / roots[b].second;
                else if (roots[a].first == b)
                    return roots[a].second;
                return -1;
            }
        };
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            UnionFind myFind(equations);
            for (int i = 0; i < values.size(); i++)
                myFind.unite(equations[i].first, equations[i].second, values[i]);
            vector<double> ans;
            for (auto& q : queries)
                ans.push_back(myFind.find(q.first, q.second));
            return ans;
        }
    };

Log in to reply
 

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