C++ union Find + hashtable

• ``````class Solution {
public:

struct Account{
string name;
set<string> emails;
Account *parent;

Account():parent(nullptr){
}

Account(string n)
:
name(n),parent(nullptr){
}

emails.insert(email);
}

for(auto &e : other->emails){
}
}

};

Account *find(Account *acc){
if(acc->parent == nullptr){
return 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;
}
else{
r1->parent = r2;
}
}

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){
}

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;
}
};
``````

• 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{} {}

_emails.insert(email);
}

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];
}
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()){
pb->_parent=pa;
} else {
pa->_parent=pb;
}
}

shared_ptr<Account> Find(shared_ptr<Account> account){
if (account->_parent){
account->_parent=Find(account->_parent);
return account->_parent;
}
return account;
}
};
``````