Krushkal's With Union-Find (path compression)

MinCostMST.py

"""
References:
https://www.youtube.com/watch?v=JZBQLXgSGfs
https://www.youtube.com/watch?v=kaBX2s3pYO4
"""
class Solution:
    
    # The purpose of find with path compression is to reduce the
    # no. of hopes needed to determine the parent node. This reduction
    # will help to decrease overall runtime from O(n) to O(log n)
    def findWithPathCompression(self, node: int, parent: Dict) -> int:
        if parent[node] == -1:
            return node
        parent[node] = self.findWithPathCompression(parent[node], parent)
        return parent[node]
    
    # Union by rank make sure to connect a lower rank absolute parent
    # to a higher rank absolute parent. This will make sure to reduce the
    # height of a "tree" formed while unifying the node. Union with rank
    # along with find with compression help to decrease overall runtime.
    # As this runtime is in order of height of tree. The goal is to
    # decrease timecomplexity from O(n) to O(log n)
    def unionByRank(self, x: int, y: int, parent: Dict, rank: Dict):
        
        # Find parents of both x and y nodes
        xparent = self.findWithPathCompression(x, parent)
        yparent = self.findWithPathCompression(y, parent)
        
        # IF not unified, unify them
        if xparent != yparent:
            
            # Find ranks of both the parents
            xrank = rank[xparent]
            yrank = rank[yparent]
            
            # If rank of parent of x is greater or equal to rank of parent of y,
            # then parent of y should point to parent of x and the overall rank of
            # parent of x is incremented by 1, visa versa.
            if xrank >= yrank:
                parent[yparent] = xparent
                rank[xparent] = rank[xparent] + 1
            else:
                parent[xparent] = yparent
                rank[yparent] = rank[yparent] + 1
                
        return
    
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        
        # If there is less than v-1 edges for v nodes
        # then there is no way to form an MST of that graph.
        # NOTE: MST of disconnected graphs are not feasible
        if len(connections) < n-1:
            return -1
        
        # Init
        nodes = set([n for n in range(1,n+1)])
        parent = {n: -1 for n in nodes}
        rank = {n: 0 for n in nodes}
        min_cost = 0
        
        # Sort all the edges in ascending order of its weights
        for (x,y,cost) in sorted(connections, key=itemgetter(2)):
            
            # Find parent of the both nodes in the connection
            xparent = self.findWithPathCompression(x, parent)
            yparent = self.findWithPathCompression(y, parent)
            
            # If they are already unified, don't consider that conncetion
            # as that will form a cycle. If not unified, add the cost
            # and unify the nodes.
            if xparent != yparent:
                min_cost = min_cost + cost
                self.unionByRank(x,y,parent,rank)
                
        return min_cost