1070. Accounts Merge

way 1a, email 作为节点, 做 union().

每个邮件数组, 所有邮件都和第一个邮件 union(), 合并社团.
把所有的邮件再 find() 一遍, father 压缩成一层, 确保小弟直接汇报给一个老大.
- 也可以找每个 mail 的老大, mail 逐个加进老大一组,
- for mail in mails: parent = find(mail); parent_child_mails[parent].append(mail);
生成结果,
根据 parent_mail, 从 mail_name 中, 找到 user_name,
parent_child_mails[parent_mail] = child mails list, 一个老大带小弟们生成一行.

数据结构:
father[node] = 老大, hashmap, 每个节点的老大.
mail_name[mail] = name, hashmap 记录邮件和人名的关系.
parent_child_mails[parent_mail] = 小弟 mail list, defaultdict(list), 老大的小弟们.

way 1b, row_id(user_id) 作为节点, 做 union().

<code>
from collections import defaultdict
class Solution:
    def accountsMerge(self, accounts):
        # init
        self.father = {}
        father = self.father
        mail_name = {}
        for rec in accounts:
            name = rec[0]
            for mail in rec[1:]:
                mail_name[mail] = name
        for mail in mail_name:
            self.father[mail] = mail
        for rec in accounts:
            mail1 = rec[1]
            for mail2 in rec[2:]:
                self.union(mail1, mail2)
        group = defaultdict(list)
        for mail in mail_name:
            father[mail] = self.find(mail)
            group[father[mail]].append(mail)
        for k in group:
            group[k].sort()
        res = []
        for k in group:
            acct_name = mail_name[group[k][0]]
            res.append([acct_name] + group[k])
        return res

    def find(self, node):
        father = self.father
        if node != father[node]:
            f = self.find(father[node])
            father[node] = f
            return f
        else:
            return node

    def union(self, a, b):
        fa = self.find(a)
        fb = self.find(b)
        if fa != fb:
            self.father[fa] = fb