【数据结构-并查集】力扣721.账户合并

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

示例 1： 输入：accounts = [[“John”, “johnsmith@mail ”, “john00@mail ”], [“John”, “johnnybravo@mail ”], [“John”, “johnsmith@mail ”, “john_newyork@mail ”], [“Mary”, “mary@mail ”]] 输出：[[“John”, ‘john00@mail ’, ‘john_newyork@mail ’, ‘johnsmith@mail ’], [“John”, “johnnybravo@mail ”], [“Mary”, “mary@mail ”]] 解释： 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 “johnsmith@mail ”。 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。 可以以任何顺序返回这些列表，例如答案 [[‘Mary’，‘mary@mail ’]，[‘John’，‘johnnybravo@mail ’]， [‘John’，‘john00@mail ’，‘john_newyork@mail ’，‘johnsmith@mail ’]] 也是正确的。

示例 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码升序进行排序。