LC 0721 [M] Accounts Merge - ALawliet/algorithms GitHub Wiki

prereq: https://github.com/codewithsenpai/algos/wiki/LC-0323-%5BM%5D-Number-of-Connected-Components-in-an-Undirected-Graph


DFS connected components on the account indexes where the neighbors are the emails


# i is the index of the account and the id, account[0] is the name for that account, account[1:] are the emails for that account
[
["John", "[email protected]", "[email protected]"], # Account i=0
["John", "[email protected]"], # Account i=1
["John", "[email protected]", "[email protected]"],  # Account i=2, note this has a common email with i=0
["Mary", "[email protected]"] # Account i=3
]

# emails_accounts_map of email to account ID
{
  "[email protected]": [0, 2],
  "[email protected]": [0],
  "[email protected]": [1],
  "[email protected]": [2],
  "[email protected]": [3]
}
class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        # [name/account, email1, email2](/ALawliet/algorithms/wiki/name/account,-email1,-email2)
        visited = [False] * len(accounts)
        email_to_accounts = defaultdict(list) # where we use account index like an account id
        res = []
        
        for i, acc in enumerate(accounts): # [name/account, email1, email2], []
            for _, email in enumerate(acc[1:]): # [email1, email2]
                email_to_accounts[email].append(i)

        def dfs(i, emails):
            visited[i] = True
            acc = accounts[i]
            for _, email in enumerate(acc[1:]):
                emails.add(email)
                for neighbor in email_to_accounts[email]:
                    if not visited[neighbor]:
                        dfs(neighbor, emails)
                    
        for i, acc in enumerate(accounts):
            name, emails = acc[0], set()
            if not visited[i]:
                dfs(i, emails)
                res.append([name] + sorted(emails))
            
        return res
class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        # i: [name/account, email1, email2, emailn...]
        visited = [False] * len(accounts)
        email_to_accounts = defaultdict(list)
        res = []
        
        for i, account in enumerate(accounts):
            for _, email in enumerate(account[1:]):
                email_to_accounts[email].append(i)

        def dfs(i, emails):
            if visited[i]: return
            visited[i] = True
            account = accounts[i]
            for _, email in enumerate(account[1:]):
                emails.add(email)
                for neighbor in email_to_accounts[email]:
                    dfs(neighbor, emails)
                    
        for i, account in enumerate(accounts):
            if not visited[i]:
                name = account[0]
                emails = set()
                dfs(i, emails)
                res.append([name] + sorted(emails))
            
        return res