题目：

  1. 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，
  2. 其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。
  4. 现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，
  5. 则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，
  6. 它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，
  7. 但其所有帐户都具有相同的名称。
  9. 合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，
  10. 其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。
  12. 例子 1:
  14. Input: 
  15. accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
  16. Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
  17. Explanation: 
  18.   第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "johnsmith@mail.com"。 
  19.   第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。
  20.   我们可以以任何顺序返回这些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
  21.   ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然会被接受。
  23. 来源：力扣（LeetCode）
  24. 链接：https://leetcode-cn.com/problems/accounts-merge
  25. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

20min,未果，逻辑错了。

  1. class UnionFind:
  2.     def __init__(self,n):
  3.         self.parent = [i for i in range(n)]
  4.         self.rank = [n-i for i in range(n)]
  5.         self.count = n
  7.     def find(self,p):
  8.         while self.parent[p] != self.parent[self.parent[p]]:
  9.             self.parent[p] = self.parent[self.parent[p]]
  10.         return self.parent[p]
  12.     def union(self,p,q):
  13.         i = self.find(p)
  14.         j = self.find(q)
  15.         if i == j:
  16.             return
  17.         if self.rank [i] < self.rank [j]:
  18.             self.parent[i] = j
  19.             self.rank [j] += self.rank [i]
  20.         else:
  21.             self.parent[j] = i
  22.             self.rank [i] += self.rank [j]
  23.         self.count -= 1
  25. class Solution:
  26.     def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
  27.         n=len(accounts)
  28.         e2name={}
  29.         e2id={}
  30.         Email=UnionFind(n)
  31.         for i in range(n):
  32.             name=accounts[i][0]
  33.             post=accounts[i][1:]
  34.             for mail in post:
  35.                 e2name[mail]=name
  36.                 if mail in e2id:
  37.                     Email.union(i,e2id[mail])
  38.                     e2id[mail]= Email.find(i)
  39.                 else:
  40.                     e2id[mail]=i
  42.         temp=collections.defaultdict(list)
  43.         for mail,index in e2id.items():
  44.             father=Email.find(index)
  45.             temp[father].append(mail)
  46.         ans=[]
  47.         for k,v in temp.items():
  48.             ans.append([accounts[k][0]]+sorted(temp[k]))
  49.         return ans

要点：

1. 并查集

如果邮箱曾经出现过，就合并，太妙了，我怎么就没想到

2. 最后还要找一下爹

不然可能还是儿子代打

3. 最后还要满足题意sort一下

4. 谁作为index

这里只有email是可以hash的，所以所有的dict都用email来做为索引去想就可以了

其他：

代码报错：无