1.题目基本信息
1.1.题目描述
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
1.2.题目地址
https://leetcode.cn/problems/accounts-merge/description/
2.解题方法
2.1.解题思路
并查集+哈希表
2.2.解题步骤
第一步，构建email->username的映射，同时构建邮箱之间的并查集（同一个账户的邮箱属于一个集合）
第二步，根据并查集的映射，构建rootEmail->emails的映射
第三步，根据rootEmail->emails的映射构建题解并返回
3.解题代码
Python代码
# # ==> 并查集模板(附优化)
class UnionFind():def __init__(self):self.roots={}self.setCnt=0 # 连通分量的个数# Union优化:存储根节点主导的集合的总节点数self.rootSizes={}def add(self,x):if x not in self.roots:self.roots[x]=xself.rootSizes[x]=1self.setCnt+=1def find(self,x):root=xwhile root != self.roots[root]:root=self.roots[root]# 优化:压缩路径while x!=root:temp=self.roots[x]self.roots[x]=rootx=tempreturn rootdef union(self,x,y):rootx,rooty=self.find(x),self.find(y)if rootx!=rooty:# 优化:小树合并到大树上if self.rootSizes[rootx]<self.rootSizes[rooty]:self.roots[rootx]=rootyself.rootSizes[rooty]+=self.rootSizes[rootx]else:self.roots[rooty]=rootxself.rootSizes[rootx]+=self.rootSizes[rooty]self.setCnt-=1from collections import defaultdictclass Solution:def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:uf=UnionFind()# 第一步，构建email->username的映射，同时构建邮箱之间的并查集（同一个账户的邮箱属于一个集合）emailToUserMap={}for account in accounts:username=account[0]firstEmail=account[1]for email in account[1:]:emailToUserMap[email]=usernameuf.add(email)uf.union(firstEmail,email) # 第二步，根据并查集的映射，构建rootEmail->emails的映射rootToEmailsMap=defaultdict(list)for email in uf.roots.keys():rootEmail=uf.find(email)rootToEmailsMap[rootEmail].append(email)# print(rootToEmailsMap)# 第三步，根据rootEmail->emails的映射构建题解并返回result=[]for key,emails in rootToEmailsMap.items():result.append([emailToUserMap[key]]+sorted(emails))# print(result)return result
4.执行结果
