<style type="text/css">
.slides {
text-align: left !important;
}
</style>
# 最小生成樹MST
#### Author:H1de_on_bruH
----
A市是一個繁榮的城市
有一天市長想要再蓋一個快速道路路網
然而有些路段的花費勢必會因為地價、技術、地形等因素而有所差異
市長想要找到一個能夠聯通所有點的最小花費
而市長聽說你是全實驗最電的競程選手 於是想請你幫他用程式來解決他的煩惱
[題目連結](https://zerojudge.tw/ShowProblem?problemid=a129)
----
## 想法1:貪心
將所有邊由權重由小排到大
一個一個看
如果邊上兩點已經是互相連通的 就不要加入這個邊
如果沒有則加入這個邊 並且同時紀錄花費
----
### 嗯?好像在哪裡看過?
如果每次都用DFS遍歷的方式檢查兩點是否連通
則複雜度會達到$O(VE)$ 這不是我們樂見的結果
檢查兩個點是否連通?聽起來很耳熟
----
### DSU加速
只要一想到這個 相信答案就呼之欲出
可以直接拿DSU模板套進來 每次查詢兩點是否在同個集合裡面
不同則連結起來
這個演算法也被叫做 **Kurskal's algorithm**
複雜度就可以壓到很健康的$O(E\log E+E\cdot \alpha(V))$
{"metaMigratedAt":"2023-06-16T20:04:53.608Z","metaMigratedFrom":"YAML","title":"最小生成樹","breaks":true,"slideOptions":"{\"theme\":\"black\",\"transition\":\"slide\"}","contributors":"[{\"id\":\"b6728096-4c9a-4b93-9b51-70c56850e20f\",\"add\":977,\"del\":282}]"}