{% tabs %} {% tab title="Python-UNION-SET" %}
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
data = []
f = [ i for i in range(n)]
size = [ 1 for i in range(n)]
def find(x):
if f[x] != x:
f[x] = find(f[x])
return f[x]
def union(x , y ):
fx = find(x)
fy = find(y)
if fx != fy :
if size[fx] >= size[fy]:
size[fx] += size[fy]
f[fy] = fx
else:
size[fy] += size[fx]
f[fx] = fy
def dist(p1,p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
for i in range(n):
for j in range(i + 1, n):
data.append((dist(points[i],points[j]),i,j))
data.sort()
ans = 0
num = 1
for da in data:
d, p1, p2 = da
if find(p1) != find(p2):
union(p1, p2)
ans += d
num += 1
if num == n:
break
return ans{% endtab %}
{% tab title="Python" %}
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
ans = 0
visit = set(list(range(len(points))))
h = [(0,0)]
while visit:
dis, np = heapq.heappop(h)
if np not in visit:
continue
visit.remove(np)
ans += dis
for nxt_p in visit:
heapq.heappush(h,(self.dist(points[np],points[nxt_p]),nxt_p))
return ans
def dist(self,p1,p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]){% endtab %} {% endtabs %}