Problem statement

https://leetcode.com/problems/connecting-cities-with-minimum-cost/

Solution

Actually what is asked in this problem is to find minimum spanning tree of given graph. We can do it with kruskal algorithm.

Complexity

Time complexity is O(E log E + n), where E is number of edges. Space complexity is O(n).

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def minimumCost(self, n, connections):
        dsu, ans = DSU(n), 0
        comps = n
        for x, y, w in sorted(connections, key = lambda x:x[2]):
            if dsu.find(x-1) == dsu.find(y-1): continue
            dsu.union(x-1, y-1)
            comps -= 1
            ans += w

        return ans if comps == 1 else -1