Manjusaka

09-15 leetcode-1584

链接 1584. Min Cost to Connect All Points

题目

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

题解

这个题一个很巧妙的解法是用并查集，将汉密尔顿距离从小到大排列，然后所有点都连接上后，就是最小花费

class UnionFind:
    def __init__(self):
        self.root = {}

    def union(self, x: int, y: int):
        self.root[self.find(x)] = self.find(y)

    def find(self, x: int) -> int:
        self.root.setdefault(x, x)
        if x != self.root[x]:
            self.root[x] = self.find(self.root[x])
        return self.root[x]


class Solution:
    def minCostConnectPoints(self, points: list[list[int]]) -> int:
        length = len(points)
        edges = []
        for i in range(length):
            for j in range(i + 1, length):
                edges.append(
                    (
                        abs(points[i][0] - points[j][0])
                        + abs(points[i][1] - points[j][1]),
                        i,
                        j,
                    )
                )
        result = 0
        uf = UnionFind()
        for value, i, j in sorted(edges, key=lambda x: x[0]):
            if uf.find(i) != uf.find(j):
                uf.union(i, j)
                result += value
        return result