Leecode #721. 账户合并

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

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

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

示例

Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation: 
  第一个和第三个 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']]仍然会被接受。

解题思路

首先读题目可知，name和email是一对多的关系且name可以重复，因此根据email可以确定一个的name。name对应的email列表中如果存在重复，则可以确定这两个name指向的是同一个用户。由此，我们可以维护一个并查集来确定name之间的关系

• 首先按照默认的顺序对name进行编号
• 通过em_to_id字典来辨认是否出现 ‘ 重复email’的情况，若存在则union这2个name的id
• 通过email -> id -> id’s parent，确定最后的输出

class DSU:
    def __init__(self, length):
        self.p = list(range(length))
    
    def find(self, x):
        root = x
        while root != self.p[root]:
            root = self.p[root]
        while x != self.p[x]:
            tmp = self.p[x]
            self.p[x] = root
            x = tmp
        return root
    
    def union(self, x, y):
        self.p[self.find(x)] = self.find(y)
        
from collections import defaultdict     
class Solution(object):
    def accountsMerge(self, accounts):
        l = len(accounts)
        dsu = DSU(l)
        em_to_id = {}
        
        for idx, acc in enumerate(accounts):
            for email in acc[1:]:
                if email in em_to_id:
                    dsu.union(em_to_id[email], idx)
                else:
                    em_to_id[email] = idx
        # then we have the relationship over names
        ans = defaultdict(list)
        # relate every email to their users' id
        for email in em_to_id:
            ans[dsu.find(em_to_id[email])].append(email)
        return [[accounts[idx][0]] + ans[idx] for idx in ans]

PS.

官方的做法用email来作为并查集中的节点，这样的做法会让并查集变得很大，占用更多的内存

find函数中可以通过压缩算法，来减少查找的时耗