Union find find (by rank) C++ solution


  • 0

    Here is my solution based on Union find by rank (http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/):

       int getRoot(int node, vector<int>& parent) {
            if (parent[node] != node)
                return parent[node] = getRoot(parent[node], parent);
            return node;
        }
    
        void unionSets(int x, int y, 
                vector<int>& parent, 
                vector<int>& rank){
            int xRoot = getRoot(x, parent),
                yRoot = getRoot(y,parent);
            if (rank[xRoot] < rank[yRoot]) {
                parent[xRoot] = yRoot;
            } else if (rank[yRoot] < rank[xRoot]) {
                parent[yRoot] = xRoot;
            } else {
                parent[yRoot] = xRoot;
                rank[xRoot]++;
            }
        }
    
        vector<vector<string> > accountsMerge(vector<vector<string> >& accounts) {
            int n = accounts.size();
            vector<int> parents(n);
            vector<int> ranks(n, 0);
            for (int i = 0; i < n; ++i) parents[i] = i;
    
            // Maps email to tree root.
            map<string, int> roots;
    
            // Union the sets.
            for (int i = 0; i < n; ++i){
                for (int j = 1; j < accounts[i].size(); ++j){
                   string& mail = accounts[i][j];
                    if (roots.count(mail)) {
                        unionSets(i, roots[mail], parents, ranks);
                    }
                    roots[mail] = getRoot(i, parents);
                }
            }
    
            // Construct the sorted list of mails per user.
            vector<vector<string> > res;
            unordered_map<int, int> treeRootToResultIndex;
            for(pair<const string, int>& i : roots) {
                int accountRoot = getRoot(i.second, parents);
                if (treeRootToResultIndex.count(accountRoot)) {
                    res[treeRootToResultIndex[accountRoot]].push_back(i.first);
                } else {
                    treeRootToResultIndex[accountRoot] = res.size();
                    res.push_back(vector<string>());
                    vector<string>& back = res.back();
                    back.push_back(move(accounts[accountRoot][0]));
                    back.push_back(move(i.first));
                }
            }
            return move(res);
        }
    

Log in to reply
 

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