联合求解的时间复杂度

以下问题的解决方案的时间复杂度是多少?如果我们假设由于路径压缩自我发现()大致分摊到O(1)

其中第一个元素accounts[i][0]是一个名称,其余元素accounts[i][0]是一个名称

现在,我们要合并这些帐户。两个帐户肯定 属于同一个人如果有一些电子邮件是共同的 两个账户。请注意,即使两个帐户具有相同的名称,它们 可能属于不同的人,因为人们可能有相同的名字。A 一个人最初可以拥有任意数量的帐户,但他们的所有帐户 帐户肯定有相同的名字。

格式:每个帐户的第一个元素是名称,其余元素是 元素是按顺序排列的电子邮件。账户本身可以 以任何顺序归还。

"john00@example.com“],[“约翰”,”johnnybravo@example.com“],[“约翰”, "johnsmith@example.com", "john\u newyork@example.com“],[“玛丽”, "mary@example.com"]]

输出:[“John”,'john00@example.com', 'john\u newyork@example.com', "mary@example.com"]]

说明:第一个约翰和第三个约翰是同一个人 “有共同的电子邮件”johnsmith@example.com". 第二个约翰和玛丽 其他账户。例如,我们可以按任何顺序返回这些列表 'john\u newyork@example.com', 'johnsmith@example.com']]仍然是 认可的。

class Solution:
    def accountsMerge(self, accounts):
        """
        :type accounts: List[List[str]]
        :rtype: List[List[str]]
        """
        owners={}
        parents={}
        merged=collections.defaultdict(set)
        results=[]

        for acc in accounts:
            for i in range(1,len(acc)):
                owners[acc[i]] = acc[0]
                parents[acc[i]] = acc[i]

        for acc in accounts:
            p = self.find(acc[1],parents) #Find parent of the first email in the list.
            for i in range(2,len(acc)):
            #Perform union find on the rest of the emails across all accounts (regardless of account name, as no common email can exist between different names.)
            #Any common emails between any 2 lists will make those 2 lists belong to the same set.
                currP = self.find(acc[i],parents)
                if p!=currP:
                    parents[currP] = p

        for acc in accounts:
            p = self.find(acc[1],parents)
            for i in range(1,len(acc)):
                merged[p].add(acc[i])        

        for name,emails in merged.items():         
            res = [owners[name]] + sorted(emails)
            results.append(res)

        return results


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