# LeetCode 1584. Min Cost to Connect All Points
https://leetcode.com/problems/min-cost-to-connect-all-points/description/
## 題目大意
給一個陣列 `points` 裡面裝著點不重複的二維座標資料
定義連結兩點的成本 (cost) 為兩點之曼哈頓距離 (Manhattan distance):
$$d(x,y) = |x_1-x_2|+|y_1-y_2|$$
回傳使所有點相連的最小成本。只要任意兩點之間恰存在一條 simple path,所有點就被視為相連。
## 思考
首先我們要搞懂題目想問的是什麼
題目有兩個關鍵線索:
1. Return the minimum cost
2. All points are connected if there is exactly one simple path between any two points
如果我們把圖畫出來就會發現,第二點就代表若視連線為圖上的邊,那個我們連線出來的結果不應該會有 cycle
這下應該就能想到本題其實要考的就是最小生成樹 (minimum spanning tree)
提到 MST 就會想到大名鼎鼎的兩個演算法:Kruskal's algorithm 與 Prim's algorithm。兩者皆是採取 greedy 的策略,前者每次選取 weight 最小的邊加入 MST;後者則可以想成是每次選能使連出去的 weight 最小的那個點
本題我們採用 Kruskal's algorithm 結合 disjoint-set,其 pseudocode 可參考下方:
<img src="https://i.stack.imgur.com/RN7h3.jpg" style="display:block;margin:auto;width:70%;height:auto;">
我們初始條件為對 $G$ 中每個點都建一個 set ($\text{Make-Set}(v)$, $\forall v\in V$),若要檢查 $\text{edge} (u, v)$在加入 $A$ (用來蒐集 MST 的邊)後是否會產生 cycle,相當於判斷 $u$ 跟 $v$ 是否在同一個 set 中,如果兩者不屬於同個 set ($\text{Find-Set} (u) \neq \text{Find-Set} (v)$),那麼我們就可以安心將 $\text{edge} (u, v)$ 加入 $A$ ($A = A\cup \{(u, v)\}$)。最後我們再使用 $\text{Union (u, v)}$ 將兩個 set 作聯集
下面提供本題我的寫法:
### Algo 1
```C++
class Edge
{
public:
int cost;
int x;
int y;
Edge() : cost(0), x(0), y(0) {}
Edge(int cost, int x, int y) : cost(cost), x(x), y(y) {}
bool operator<(const Edge &e) const { return cost < e.cost; }
Edge &operator=(const Edge &e)
{
if (this != &e)
{
cost = e.cost;
x = e.x;
y = e.y;
}
return *this;
}
};
class Solution
{
public:
int minCostConnectPoints(vector<vector<int>> &points)
{
size_t n = points.size();
vector<Edge> edge(n * (n - 1) / 2);
for (int i = 0, k = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int x1 = points[i][0], x2 = points[j][0];
int y1 = points[i][1], y2 = points[j][1];
int d = abs(x1 - x2) + abs(y1 - y2);
edge[k++] = Edge(d, i, j);
}
}
sort(edge.begin(), edge.end());
vector<int> p(n), rank(n, 0);
iota(p.begin(), p.end(), 0); // 填入遞增
int ans = 0, count = 0;
for (auto &e : edge)
{
int rx = find(p, e.x), ry = find(p, e.y);
if (rx == ry)
continue;
ans += e.cost;
if (rank[rx] < rank[ry])
swap(rx, ry);
p[rx] = ry; // 合併
rank[ry] += (rank[rx] == rank[rx]);
if (++count == n - 1)
break;
}
return ans;
}
private:
// Disjoint Set Union -- find()
int find(vector<int> &parent, int x)
{
while (parent[x] != x) // 當 x 並非集合之根元素
{
int temp = parent[x];
parent[x] = parent[parent[x]];
x = temp;
}
return x;
}
};
```
***
### Algo 2
一樣的核心精神,不過這個寫法可能會再更平易近人些
```C++
class Solution
{
public:
int dist(int x1, int y1, int x2, int y2)
{
return abs(x1 - x2) + abs(y1 - y2);
}
int minCostConnectPoints(vector<vector<int>> &points)
{
size_t n = points.size();
vector<int> edge(n, 0);
int ans = 0;
edge[0] = INT_MAX;
for (auto i = 1; i < n; i++)
edge[i] = dist(points[0][0], points[0][1], points[i][0], points[i][1]);
for (int i = 1; i < n; i++)
{
auto it = min_element(edge.begin(), edge.end());
ans += *it;
int index = it - edge.begin();
*it = INT_MAX;
for (auto i = 0; i < n; i++)
{
if (edge[i] == INT_MAX)
continue;
edge[i] = min(edge[i], dist(points[i][0], points[i][1], points[index][0], points[index][1]));
}
}
return ans;
}
};
```
## 簡單補充
### 最小生成樹 (Minimum Spanning Tree)
【定義】
給定 $G = (V,E)$ 為一個 undirected weighted graph
1. 若 $H$ 為 $G$ 之一 spanning subgraph 且 $H$ 為 tree,則稱 $H$ 為 $G$ 之 spanning tree
2. 假設 $T = (V,E')$ 為 $G$ 之一 spanning tree,定義 $T$ 之 weight $w(T) = \sum\limits_{e\in E'}w(e)$,其中 $w(e)$ 為 $e$ 之 weight
3. 若 $T$ 為 $G$ 的 spanning tree 中具有最小權重者,則稱 $T$ 為 $G$ 之 minimum spanning tree