Hi 大家好，今天要來挑戰Union-Find的進階題。
要找出在哪邊使用union-find是這題的挑戰，讓我們速戰速決吧。

Leetcode 721. Accounts Merge

題目敘述：
有一個巢狀的list，accounts，裡面每一個list都保存了使用者以及屬於使用者的email帳號。可是不同的list中的使用者可能是同一人。我們要想辦法將同一個使用合併到一個list中，並且是排序好的，並且最前面是使用者的名字。

Example:

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

example解釋：accounts中有三個使用者都叫John的list，其中前兩個都叫John的使用者「都有」"johmsmith@mail.com"這個email帳號，所以認定這兩個John是同一人；而最後一個John的list中的email帳號和前面兩個完全沒有共同的帳號，所以認定是不同人。

分析：
根據上面的範例，當我們察覺到某一list中的帳號和別列中的帳號相同時，代表這兩個list屬於同一使用者可以合併。但是要直接合併有點困難，因為可能有好幾個list要合併成一個list，並且最前面是使用者的名字，後面是排序好的email帳號。..這程式感覺有點難寫，不如我們...先對他們的proxy（代理人）合併，於是我們要利用每個list在accounts中的index來代表這些list中的email帳號來自哪個Group，當某個email帳號會出現在不同的list中時，我們就將這些index union。

我們同時要紀錄哪些email屬於哪個index，但會讓同時屬於不同index的email帳號只屬於第一次被拜訪到的index，也會排除使用者的名字，形成一張hashmap。

我會針對這張hashmap中的key利用find找出他們的Root是誰，並且將Root底下的帳號都加入到key等於Root的list中。並且紀錄下那些Root是誰。

最後我們將Root在accounts中的使用者名字和被排序過的email帳號相接起來。

class UnionFind:
    def __init__(self, n):
        self.par = {i : i for i in range(n)}
        self.rank = [1] * n
    
    def find(self, x):
        p = self.par[x]
        while p != self.par[p]:
            self.par[p] = self.par[self.par[p]]
            p = self.par[p]
        return p
    
    def union(self, x1, x2):
        y1, y2 = self.find(x1), self.find(x2)

        if y1 == y2:
            return
        
        if self.rank[y1] > self.rank[y2]:
            self.par[y2] = y1
        elif self.rank[y2] > self.rank[y1]:
            self.par[y1] = y2
        else:
            self.par[y2] = y1
            self.rank[y1] += 1

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        accountToIndex = {}
        indexToEmail = defaultdict(list)
        uf = UnionFind(len(accounts))

        for i, acc in enumerate(accounts):
            for a in acc[1:]:
                if a in accountToIndex:
                    uf.union(i, accountToIndex[a])
                else:
                    accountToIndex[a] = i
                    indexToEmail[i].append(a)
        merge = []
        keys = list(indexToEmail.keys())
        for key in keys:
            leader = uf.find(key)
            if leader not in merge:
                merge.append(leader)
            if key != leader:
                indexToEmail[leader] += indexToEmail[key]
        
        res = []
        for i in merge:
            res.append([accounts[i][0]] + sorted(indexToEmail[i]))
        
        return res

我們朝著目標和夢想前進的過程並非筆直的，而是有時蜿蜒曲折有時高低起伏的三度空間軌跡，最後可能是落在離目標較近、較遠、較高、較低的位置都或是完全重疊但是這些途中的軌跡才是生命精彩的地方。