C++ union Find + hashtable


  • 1
    G
    class Solution {
    public:
        
        struct Account{
          string name;
          set<string> emails;
          Account *parent;
        
          Account():parent(nullptr){
          }
            
          Account(string n)
              :
              name(n),parent(nullptr){
              }
            
         void addEmail(const string &email){
             emails.insert(email);
          }
        
          void addEmails(Account *other){
              for(auto &e : other->emails){
                  addEmail(e);
              }
          }
        
        };
        
        Account *find(Account *acc){
            if(acc->parent == nullptr){
                return acc;
            }
            
            acc->parent->addEmails(acc);
            acc->parent = find(acc->parent);
            return acc->parent;
        }
        
        void Union(Account *a1, Account *a2){
    
            Account *r1 = find(a1);
            Account *r2 = find(a2);
                
            if(r1 == r2){
                return;
            }
            
            if(r1->emails.size() > r2->emails.size()){
                r2->parent = r1;
                r1->addEmails(r2);
            }
            else{
               r1->parent = r2;
               r2->addEmails(r1);
            }
        }
        
        vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
            unordered_map<string,Account*> mailToAccount;
            
            for(auto &a : accounts){
                Account *acc = new Account(a[0]);
                for(int i = 1; i < a.size(); ++i){
                    acc->addEmail(a[i]);
                }
                
                for(auto &email : acc->emails){
                    if(mailToAccount.find(email) == mailToAccount.end()){
                        mailToAccount[email] = acc;
                    }
                    else{
                        Union(mailToAccount[email],acc);
                        mailToAccount[email] = find(acc);
                    }
                }
            }
            
            unordered_set<Account *> visited;
            for(auto &p : mailToAccount){
                visited.insert(find(p.second));
            }
                
            vector<vector<string> > result;
            for(auto &a : visited){
                vector<string> temp;
                temp.push_back(a->name);
                for(auto &s : a->emails){
                    temp.push_back(s);
                }
                
                result.push_back(temp);
            }
            
            return result;
        }
    };
    

  • 0

    Hi @galster, thanks for sharing this solution. It is easy to understand. Similar C++11 solution is below.

    class Solution {
    public:
        class Account {
        public:
            shared_ptr<Account> _parent;
            string _name;
            set<string> _emails;
            
            Account(string name) : _parent{nullptr}, _name{name}, _emails{} {}
            
            void AddEmail(string email){
                _emails.insert(email);
            }
            
            void AddEmails(set<string>& emails){
                for (auto &&email: emails)
                    _emails.insert(email);
            }
        };
        
        vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
            vector<vector<string>> res{};
            vector<shared_ptr<Account>> va{}; // vector<vector<string>> to vector<shared_ptr<Account>>
            for (auto &&account: accounts){
                auto a=make_shared<Account>(account[0]);
                for (int i=1; i<account.size(); ++i){
                    string email=account[i];
                    a->AddEmail(email);
                }
                va.push_back(a);
            }
            unordered_map<string,shared_ptr<Account>> hash{}; // hash collisions are unioned (key=email val=ptr to Account)
            for (auto &&a: va){
                for (auto &&email: a->_emails){
                    if (hash.find(email)==hash.end()){
                        hash[email]=a;
                    } else {
                        auto b=hash[email];
                        Union(a,b);
                    }
                }
            }
            unordered_set<shared_ptr<Account>> disjoint{}; // disjoint sets to vector<vector<string>> res
            for (auto &&a: hash){
                auto parent=Find(a.second);
                disjoint.insert(parent);
            }
            for (auto &&a: disjoint){
                vector<string> merged{a->_name};
                for (auto &&email: a->_emails){
                    merged.push_back(email);
                }
                res.push_back(merged);
            }
            return res;
        }
    
        void Union(shared_ptr<Account> a, shared_ptr<Account> b){
            shared_ptr<Account> pa=Find(a);
            shared_ptr<Account> pb=Find(b);
            if (pa==pb) return;
            if (pa->_emails.size() > pb->_emails.size()){
                pa->AddEmails(pb->_emails);
                pb->_parent=pa;
            } else {
                pb->AddEmails(pa->_emails);
                pa->_parent=pb;
            }
        }
        
        shared_ptr<Account> Find(shared_ptr<Account> account){
            if (account->_parent){
                account->_parent=Find(account->_parent);
                return account->_parent;
            }
            return account;
        }
    };
    

  • 0
    G

    @claytonjwong glad you liked it. Thanks for sharing your solution.


Log in to reply
 

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