題目描述

克魯斯克爾演算法 (Kruskal) 演算法是一種用來尋找最小生成樹的演算法，由 Joseph Kruskal 在1956年發表。

步驟：

1. 新建圖G，G中擁有原圖中相同的節點，但沒有邊
2. 將原圖中所有的邊按權值從小到大排序
3. 從權值最小的邊開始，如果這條邊連接的兩個節點於圖G中不在同一個連通分量中，則添加這條邊到圖G中
4. 重複3，直至圖G中所有的節點都在同一個連通分量中

例題參考：克魯斯克爾演算法

輸入格式

第一行 2個整數，分別是 點數 N 和 邊數 M

接下來有 M行，每一行上會有三個整數 u, v, w，依序加入點 u 連接到 點 v, 無向邊權重 w。節點編號為 0 ... N-1。

輸出格式

輸出最小生成樹各邊(u, v, w) 及 權重之和

Samples

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11

(2, 4, 5)
(0, 3, 5)
(3, 5, 6)
(1, 4, 7)
(0, 1, 7)
(4, 6, 9)
39

原始資料

• Zero1 題號：b007
• Hydro 題號：Z1007
• Locale：zh_TW
• Display：open