LC721. Accounts Merge

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        """
        DFS way
        1. build graph email: acnt, vitsit_acnt set to avoid cycle 
        2. dfs traverse email and its owner's other accnt, record path emails and  skip visited acnt
        3.  each time one acnt have done dfs, add sorted 
        emails into res 
        """
        res = []
        em2ac = collections.defaultdict(list) # graph
        seen_acc = set()
        # build graph 
        for i, acc in enumerate(accounts):
            for j in range(1,len(acc)):
                em = acc[j]
                em2ac[em].append(i)
        #print(em2ac)
        # @emails: set(), for temporary cache emails belong to same user 
        def dfs(emails, acc):
            
            if acc in seen_acc:
                return 
            seen_acc.add(acc)
            for j in range(1, len(accounts[acc])):
                email = accounts[acc][j]
                emails.add(email)
                for nei in em2ac[email]:
                    dfs(emails,nei)
        for i in range(len(accounts)):
            # note need to recheck cases when account has no other ownership 
            if i in seen_acc:
                continue
            emails = set()
            name = accounts[i][0]
            dfs(emails,i)
            res.append([name]+sorted(emails))
        return res 

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        """
        DFS way
        1. build graph email: acnt, vitsit_acnt set to avoid cycle 
        2. dfs traverse email and its owner's other accnt, record path emails and  skip visited acnt
        3.  each time one acnt have done dfs, add sorted 
        emails into res 
        """
        email_name = {}
        res = []
        em2ac = collections.defaultdict(set) # graph
        #seen_acc = set()
        seen_email = set()
        # build graph 
        for i, acc in enumerate(accounts):
            name = acc[0]
            for j in range(1,len(acc)):
                em = acc[j]
                email_name[em] = name 
               # em2ac[em].add(i)
                em2ac[em].add(acc[1])
                em2ac[acc[1]].add(em)
        # print(em2ac)
        # print(email_name)
        # @emails: set(), for temporary cache emails belong to same user 
        def dfs(emails, em):
            if em in seen_email:
                return 
            seen_email.add(em)
            emails.add(em)
            for nei in em2ac[em]:
                if nei not in seen_email:
                    dfs(emails,nei)
                        
        for email in email_name:
            # note need to recheck cases when account has no other ownership 
            if email in seen_email:
                continue
            emails = set()
            name = email_name[email]
            dfs(emails,email)
            res.append([name]+sorted(emails))
        return res 

class UF:
    def __init__(self,n):
        self.p = list(range(n))
        self.ranks = [1] * n 
    def find(self,u):
        if u != self.p[u]:
            self.p[u] = self.find(self.p[u])
        return self.p[u]
    def union(self,u,v):
        pu,pv = self.find(u),self.find(v)
        if pu == pv :
            return False 
        elif pu > pv:
            self.p[pv] = pu
            self.ranks[pu] += self.ranks[pv]
        elif pu < pv:
            self.p[pu] = pv
            self.ranks[pv] += self.ranks[pu]
        return True 
    
class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        """
        UF
        1 traverse all emails, if current email not seen, put in
        """
        n = len(accounts)
        uf = UF(n)
        mail2idx = {}
        res = []
        for i in range(n):
            for idx , email in enumerate(accounts[i]):
                if idx == 0 :
                    continue 
                if email not in mail2idx:
                    mail2idx[email] = i 
                else:
                    pre_idx = mail2idx[email]
                    uf.union(pre_idx,i)
        # @sets:   parent_idx:  emails 
        sets = collections.defaultdict(set)
        for i in range(n):
            parent_idx = uf.find(i)
            for j in range(1, len(accounts[i])):
                email = accounts[i][j]
                sets[parent_idx].add(email)
        for i, emails in sets.items():
            name = accounts[i][0]
            res.append([name]+sorted(list(emails)))
        return res