leetcode-MST(Kruskal's alg)

1135. Connecting Cities With Minimum Cost.py

class UnionFindSet:
    def __init__(self, n):
        self._parents = [i for i in range(n)]
        self._ranks = [1 for _ in range(n)]
    
    def find(self, u):
        while u != self._parents[u]:
            self._parents[u] = self._parents[self._parents[u]]
            u = self._parents[u]
        return u
    
    def union(self, u, v):
        root_u, root_v = self.find(u), self.find(v)
        if root_u == root_v:
            return True
        
        if self._ranks[root_u] < self._ranks[root_v]:
            self._parents[root_u] = root_v
        elif self._ranks[root_v] < self._ranks[root_u]:
            self._parents[root_v] = root_u
        else:
            self._parents[root_u] = root_v
            self._ranks[root_v] += 1
            
        return False
    
class Solution:
    def minimumCost(self, N: int, connections: List[List[int]]) -> int:
        """
        Problem formulation:
            We could formulate this problem into minimum spanning tree problem. So, our goal turn to if it's possble to construct minimum spanning tree given an undirected graph. If yes, return weight. Otherwise, return -1.
        
        Thought process:
            We use Kruskal's algorithm
            Step1: sorted the edges by their weight in an increasing order
            Step2: It's a greedy algorithm. We iterate the soreted edge, at each step we connected them together, and keep calculated the cost from node a node b, if they're not connected before.
            Step3: We make sure if there's only one group of connected components by checking if all the root nodes of nodes in the union-find set is the same root node. Otherwise, return -1.
        
        Time complexity analysis:
            For step1, because we sort the edge by their weight, it's O(mlogm)
            For step2, merge and find take O(log * n) =~O(1)
            So, toally, it should be O(mlogm)
            
        Note:
            1.Kruskal's algorithm is implemented using Union-Find Data Structure practically.
            2.It's greedy algorithm and proves more efficient on sparse graphs compared to Prim's algorithm
            
        T:O(mlogm)
        S:O(n) because we need maiting array tree when implement union-find
        """
        connections = sorted(connections, key = lambda x: x[2])
        unionfind = UnionFindSet(N)
        cost = 0
        for a, b, w in connections:
            if not unionfind.union(a-1, b-1):
                cost += w
        return -1 if len(set([unionfind.find(n) for n in range(N)])) != 1 else cost