721. Accounts Merge

https://leetcode.com/problems/accounts-merge/

solution

• 并查集

# https://leetcode.com/problems/accounts-merge/solutions/1084738/python-the-clean-union-find-solution-you-are-looking-for/

class UF:
    def __init__(self, n):
        self.parents = list(range(n))

    def union(self, child, parent):
        self.parents[self.find(child)] = self.find(parent)

    def find(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        uf = UF(n=len(accounts))

        email_to_index = {}
        for i, account in enumerate(accounts):
            emails = account[1:]
            for email in emails:
                if email in email_to_index:
                    uf.union(i, email_to_index[email])
                email_to_index[email] = i

        ans = collections.defaultdict(list)
        for email, index in email_to_index.items():
            ans[uf.find(index)].append(email)

        return [[accounts[i][0]] + sorted(emails) for i, emails in ans.items()]

时间复杂度：O() 空间复杂度：O()

• dfs

"""
# https://zhuanlan.zhihu.com/p/60635925
# emails_accounts_map of email to account ID
{
  "[e-mail]": [0, 2],
  "[e-mail]": [0],
  "[e-mail]": [1],
  "[e-mail]": [2],
  "[e-mail]": [3]
}
"""

from collections import defaultdict

class Solution(object):
    def accountsMerge(self, accounts):
        visited_accounts = [False] * len(accounts)
        emails_accounts_map = defaultdict(list)
        res = []

        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                email = account[j]
                emails_accounts_map[email].append(i)

        def dfs(i, emails):
            if visited_accounts[i]:
                return
            visited_accounts[i] = True
            for j in range(1, len(accounts[i])):
                email = accounts[i][j]
                emails.add(email)
                for neighbor in emails_accounts_map[email]:
                    dfs(neighbor, emails)

        for i, account in enumerate(accounts):
            if visited_accounts[i]:
                continue
            name = account[0]
            emails = set()
            dfs(i, emails)
            res.append([name] + sorted(emails))
        return res

• 集合

# 注意这里的dict如何解决多个相同的key同时存在字典中: dict[str, list[list[str]]]
# 同时, 一个错误思路是, 每次去历史列表里找，找不到则新加一个list, 可能现在找不到，但未来有别的牵桥搭线就可以找到

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        from collections import defaultdict
        if not accounts:
            return
        lookup = defaultdict(list)
        res = []
        for account in accounts:
            name = account[0]
            email = set(account[1:])

            lookup[name].append(email)
            for e in lookup[name][:-1]:
                # a\b\c搭桥相连, a:123, b:45, c:15
                # a先进入c, 之后b并入c.
                if e & email:
                    lookup[name].remove(e)
                    lookup[name][-1].update(e)

        for key, val in lookup.items():
            for tmp in val:
                res.append([key] + list(sorted(tmp)))
        return res

• bfs