【アルゴリズム——Python実装】調査と最適化

class UnionFind(object):
    """
    Quick Find
    """
    def __init__(self, n):
        #        n，  id             
        self.count = n
        self.id = range(n)

    def find(self, p):
        #         
        if p >= 0 and p < self.count:
            return self.id[p]

    def isConnected(self, p, q):
        # p q        ，            
        return self.find(p) == self.find(q)

    def unionElements(self, p, q):
        # p q  
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            # pq    ，    ，    
            return None
        i = 0
        while i < self.count:
            if self.id[i] == pID:
                self.id[i] = qID
            i += 1

class UnionFind2(object):
    """
    Quick Union，        （  ）      ，     （  ）  
    """
    def __init__(self, n):
        #        n，  id             
        self.count = n
        self.parent = range(n)
        self.sz = [1 for _ in range(n)] # sz[i]   i          

    def find(self, p):
        #         
        if p >=0 and p < self.count:
            while p != self.parent[p]:
                #         ，            ，      
                #       ，       
                p = self.parent[p]
            return p

    def isConnected(self, p, q):
        # p q        ，            
        #   p q            
        return self.find(p) == self.find(q)

    def unionElements(self, p, q):
        # p q  
        pRoot = self.find(p)
        qRoot = self.find(q)
        if pRoot == qRoot:
            # pq       ，    ，    
            return None
        if self.sz[pRoot] < self.sz[qRoot]:
            self.parent[pRoot] = qRoot
            self.sz[qRoot] += self.sz[pRoot]
        else:
            self.parent[qRoot] = pRoot
            self.sz[pRoot] += self.sz[qRoot]

class UnionFind3(object):
    """
    Quick Union，        （  ）      ，     （  ）  
    """
    def __init__(self, n):
        #        n，  id             
        self.count = n
        self.parent = range(n)
        self.rank = [1 for _ in range(n)] # rank[i]   i            

    def find(self, p):
        #         
        if p >=0 and p < self.count:
            while p != self.parent[p]:
                #         ，            ，      
                #       ，       
                p = self.parent[p]
            return p

    def isConnected(self, p, q):
        # p q        ，            
        #   p q            
        return self.find(p) == self.find(q)

    def unionElements(self, p, q):
        # p q  
        pRoot = self.find(p)
        qRoot = self.find(q)
        if pRoot == qRoot:
            # pq       ，    ，    
            return None
        if self.rank[pRoot] < self.rank[qRoot]:
            #      rank，  rank[i]  i          。
            # pRoot  qRoot ，qRoot     ，pRoot      qRoot， find       pRoot
            self.parent[pRoot] = qRoot
        elif self.rank[pRoot] > self.rank[qRoot]:
            self.parent[qRoot] = pRoot
        else:
            self.parent[pRoot] = qRoot
            self.rank[qRoot] += 1

class UnionFind4(object):
    """
        Path Compression，Quick Union，        （  ）      ，     （  ）  
    """
    def __init__(self, n):
        #        n，  id             
        self.count = n
        self.parent = range(n)
        self.rank = [1 for _ in range(n)] # rank[i]   i            

    def find(self, p):
        #         
        if p >=0 and p < self.count:
            while p != self.parent[p]:
                #         ，            ，      
                #       ，       
                #     ，                 
                self.parent[p] = self.parent[self.parent[p]]
                p = self.parent[p]
            return p

    def isConnected(self, p, q):
        # p q        ，            
        #   p q            
        return self.find(p) == self.find(q)

    def unionElements(self, p, q):
        # p q  
        pRoot = self.find(p)
        qRoot = self.find(q)
        if pRoot == qRoot:
            # pq       ，    ，    
            return None
        if self.rank[pRoot] < self.rank[qRoot]:
            #      rank，  rank[i]  i          。
            # pRoot  qRoot ，qRoot     ，pRoot      qRoot， find       pRoot
            self.parent[pRoot] = qRoot
        elif self.rank[pRoot] > self.rank[qRoot]:
            self.parent[qRoot] = pRoot
        else:
            self.parent[pRoot] = qRoot
            self.rank[qRoot] += 1


class UnionFind5(object):
    """
        Path Compression，Quick Union，        （  ）      ，     （  ）  
    """
    def __init__(self, n):
        #        n，  id             
        self.count = n
        self.parent = range(n)
        self.rank = [1 for _ in range(n)] # rank[i]   i            

    def find(self, p):
        #         
        if p >=0 and p < self.count:
            #     ，             
            if p != self.parent[p]:
                self.parent[p] = self.find(self.parent[p])
            return self.parent[p]

    def isConnected(self, p, q):
        # p q        ，            
        #   p q            
        return self.find(p) == self.find(q)

    def unionElements(self, p, q):
        # p q  
        pRoot = self.find(p)
        qRoot = self.find(q)
        if pRoot == qRoot:
            # pq       ，    ，    
            return None
        if self.rank[pRoot] < self.rank[qRoot]:
            #      rank，  rank[i]  i          。
            # pRoot  qRoot ，qRoot     ，pRoot      qRoot， find       pRoot
            self.parent[pRoot] = qRoot
        elif self.rank[pRoot] > self.rank[qRoot]:
            self.parent[qRoot] = pRoot
        else:
            self.parent[pRoot] = qRoot
            self.rank[qRoot] += 1