1135. Connecting Cities With Minimum Cost

Link

MST

Kruskal

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:

        if n == 1:
            return 0

        parents = list(range(n+1))

        def find(x):
            if x != parents[x]:
                parents[x] = find(parents[x])

            return parents[x]

        def union(x,y):
            x = find(x)
            y = find(y)

            if x < y:
                parents[y] = x
            else:
                parents[x] = y

        connections.sort(key=lambda x: x[2])

        res = 0

        for [v1, v2, w] in connections:
            if find(v1) != find(v2):
                union(v1, v2)
                res += w
        
        for i in range(1, n+1):
            if find(i) != 1:
                return -1

        return res