POJ1679 The Unique MST

對MST的認識僅僅kruskal算法而已

用最近這段時間把prim, 和一些MST相關題目寫一寫~

連結：POJ1679 The Unique MST

題目：

顧名思義，判斷最小生成樹是否唯一

做法：

最直覺的方法應該是求次小生成樹，然後判斷花費是否與最小生成樹相同

若相同則代表非唯一

但我還不會次小生成樹QQ，這裡用另一個方法

如果不是唯一

代表有一條權重W的邊在生成樹上，且樹外有條權重亦為W的替代道路

在邊數不大的情況下，判斷有沒有相同W的邊很容易

剛好我建MST是用Kruskal，排序後順便O(E)可以解決，不用O(E^2)檢查

要判斷對於權重W是否有替代道路，最直接的方式就是把原先W的邊拔掉

重建後判斷花費是否與原先的最小生成樹相同

若所有重建後的花費皆與原花費不同則唯一，反之則不唯一
總複雜度是O(VE)，原題說最多100個點，那E會小於100^2

寫完這題也知道了一個性質
若一張圖上沒有任何相同邊權的邊，則這張圖的MST唯一。

code:
num_ban代表樹上有多少邊其權重是樹外也有的，每條都拔拔看然後重建樹