# 92ms beats 92.12% with union find

• ``````For example:
data:{name1,mail1,mail2},{name1,mail1,mail3},{name1,mail4},{name2,mail5}

DATA structure:
hash:
key   value(key)   value(value)
name1    mail1         id1
mail2         id1
mail3         id2
mail4         id3
name2    mail5         id4

idx:
id: id1 id2 id3 id4
id1 id1 id3 id4
``````
``````typedef map<string,int> mtype;
class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
map<string,mtype >hash;
vector<pair<int,int> >idx;
for(int i=0;i<accounts.size();i++){//for1
string name=accounts[i][0];
idx.push_back(pair<int,int>(i,1));
bool f=(hash.find(name)==hash.end());
for(int j=1;j<accounts[i].size();j++){//for2
string mail=accounts[i][j];
if(f)hash[name][mail]=i;
else{//else1
mtype::iterator it=hash[name].find(mail);
if(it==hash[name].end())hash[name][mail]=i;
else{
int id1=find(it->second,idx),id2=find(i,idx);
if(idx[id1].second<idx[id2].second){
idx[id1].first=id2;
idx[id2].second+=idx[id1].second;
}else{
idx[id2].first=id1;
idx[id1].second+=idx[id2].second;
}
}
}//else1
}//for2
}//for1
vector<vector<string> >res;
for(auto it=hash.begin();it!=hash.end();it++){
map<int,int>hasht;
for(auto it2=it->second.begin();it2!=it->second.end();it2++){
int id=find(it2->second,idx);
if(hasht.find(id)==hasht.end()){
res.push_back(vector<string>{it->first,it2->first});
hasht[id]=res.size()-1;
}else res[hasht[id]].push_back(it2->first);
}
}
return res;
}//func
int find(int id,vector<pair<int,int> >&idx){
while(id!=idx[id].first){
idx[id].first=idx[idx[id].first].first;
id=idx[id].first;
}
return id;
}
};
``````

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