【数据结构-并查集】力扣721. 账户合并
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
示例 1：
输入：accounts = [[“John”, “johnsmith@mail.com”, “john00@mail.com”], [“John”, “johnnybravo@mail.com”], [“John”, “johnsmith@mail.com”, “john_newyork@mail.com”], [“Mary”, “mary@mail.com”]]
输出：[[“John”, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’], [“John”, “johnnybravo@mail.com”], [“Mary”, “mary@mail.com”]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 “johnsmith@mail.com”。
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [[‘Mary’，‘mary@mail.com’]，[‘John’，‘johnnybravo@mail.com’]，
[‘John’，‘john00@mail.com’，‘john_newyork@mail.com’，‘johnsmith@mail.com’]] 也是正确的。
示例 2：
输入：accounts = [[“Gabe”,“Gabe0@m.co”,“Gabe3@m.co”,“Gabe1@m.co”],[“Kevin”,“Kevin3@m.co”,“Kevin5@m.co”,“Kevin0@m.co”],[“Ethan”,“Ethan5@m.co”,“Ethan4@m.co”,“Ethan0@m.co”],[“Hanzo”,“Hanzo3@m.co”,“Hanzo1@m.co”,“Hanzo0@m.co”],[“Fern”,“Fern5@m.co”,“Fern1@m.co”,“Fern0@m.co”]]
输出：[[“Ethan”,“Ethan0@m.co”,“Ethan4@m.co”,“Ethan5@m.co”],[“Gabe”,“Gabe0@m.co”,“Gabe1@m.co”,“Gabe3@m.co”],[“Hanzo”,“Hanzo0@m.co”,“Hanzo1@m.co”,“Hanzo3@m.co”],[“Kevin”,“Kevin0@m.co”,“Kevin3@m.co”,“Kevin5@m.co”],[“Fern”,“Fern0@m.co”,“Fern1@m.co”,“Fern5@m.co”]]
提示：
1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0] 由英文字母组成
accounts[i][j] (for j > 0) 是有效的邮箱地址
并查集
class UnionFind{
private:
vector<int> parent;
public:
UnionFind(int n){
parent.resize(n);
for(int i = 0; i < n; i++){
parent[i] = i;
}
}
void unite(int index1, int index2){
parent[find(index2)] = find(index1);
}
int find(int index){
if(parent[index] == index){
return index;
}
parent[index] = find(parent[index]);
return parent[index];
}
};
class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
map<string, int> emailToIndex;
unordered_map<string, string> emailToName;
int emailsCount = 0;
for(auto& account : accounts){
string& name = account[0];
for(int i = 1; i < account.size(); i++){
string& email = account[i];
if(!emailToIndex.contains(email)){
emailToIndex[email] = emailsCount++;
emailToName[email] = name;
}
}
}
UnionFind uf(emailsCount);
for(auto& account : accounts){
string& firstEmail = account[1];
int firstIndex = emailToIndex[firstEmail];
for(int i = 2; i < account.size(); i++){
string& nextEmail = account[i];
int nextIndex = emailToIndex[nextEmail];
uf.unite(firstIndex, nextIndex);
}
}
unordered_map<int, vector<string>> indexToEmails;
for(auto& [email, index] : emailToIndex){
indexToEmails[uf.find(index)].emplace_back(email);
}
vector<vector<string>> ans;
for(auto& [_, emails] : indexToEmails){
vector<string> account;
account.emplace_back(emailToName[emails[0]]);
for(auto& email : emails){
account.emplace_back(email);
}
ans.emplace_back(account);
}
return ans;
}
};
这道题我们定义一个容器emailToIndex和一个变量emailsCount，我们通过遍历acounts中各个账户的邮箱来统计总共有多少邮箱，当遍历某一个邮箱的时候，如果该邮箱已经在emailToIndex中出现，那么我们就不记录他，如果没出现过，就让emailsCount++，并且给emails定义他的Index储存在emailToIndex中，并且再定义一个容器emailToName来记录某个email到底是哪个人的。
记录完emailsCount了后，将它传入并查集的中，resize并查集的parent大小为emailsCount。接下来再次遍历每个账户的邮箱，我们通过unite函数，将parent中各个email对于的index的父节点都指向他们的代表节点find(firstIndex)。最后parent中元素相同的email代表是一个人名下的email。
我们再定义一个indexToEmail函数来储存parent中的代表节点，他的大小就是人数的大小。我们遍历emailsToIndex中的每一个邮箱，将他们记录到indexToEmail对应的代表节点中。
最后我们要记录答案，只需要遍历indexToEmails，通过emailToName查询每个代表节点对应的名字，然后将该代表节点下的所有邮箱都加入到该名字所在的容器中即可。
有一个需要注意的是，emailToIndex的map不能改成哈希表，这是因为题目要求邮箱按照ascii码排序，而map中的键如果是string，则自动按照ascii码升序进行排序。