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

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

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

示例 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’]] 也是正确的。

提示：

accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。

解法一：并查集

同一个account中的account[1]与剩余的account[2:]为联通关系。为所有的email建立并查集，利用account中保存的联通关系进行union操作。需要为每个email分配id，并记录其对应的用户名。这样遍历并查集中的id值，可以根据email_to_name[emails[root_id]]和emails[id]生成结果。

  1. class UF:
  2.     def __init__(self, n):
  3.         self.id = [i for i in range(n)]
  4.         self.sz = [1 for _ in range(n)]
  5.         self.count = n
  7.     def find(self, p):
  8.         while p != self.id[p]:
  9.             p = self.id[p]
  10.         return p
  12.     def connected(self, p, q):
  13.         return self.find(p) == self.find(q)
  15.     def union(self, p, q):
  16.         p_id, q_id = self.find(p), self.find(q)
  17.         if p_id == q_id:
  18.             return
  19.         if self.sz[p_id] < self.sz[q_id]:
  20.             self.id[p_id] = q_id
  21.             self.sz[q_id] += self.sz[p_id]
  22.         else:
  23.             self.id[q_id] = p_id
  24.             self.sz[p_id] += self.sz[q_id]
  25.         self.count -= 1
  27. class Solution:
  28.     def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
  29.         email_to_name = {}
  30.         email_to_idx = {}
  31.         emails = []
  32.         i = 0
  33.         for account in accounts:
  34.             name = account[0]
  35.             for email in account[1:]:
  36.                 if email not in email_to_name:
  37.                     email_to_name[email] = name
  38.                 if email not in email_to_idx:
  39.                     email_to_idx[email] = i
  40.                     i += 1
  41.                     emails.append(email)
  42.         uf = UF(len(emails))
  43.         for account in accounts:
  44.             if len(account) > 2:
  45.                 idx_1 = email_to_idx[account[1]]
  46.                 for email in account[2:]:
  47.                     idx_2 = email_to_idx[email]
  48.                     uf.union(idx_1, idx_2)
  49.         res = {}
  50.         for i in range(len(emails)):
  51.             root = uf.find(i)
  52.             res.setdefault(root, []).append(emails[i])
  53.         return [[email_to_name[v[0]]] + sorted(v) for v in res.values()]