UVA 1395: Slim Span - 最小苗條度生成樹（Kruskal 變體）

問題描述

給定無向加權圖，求生成樹中「苗條度」（最大邊權 - 最小邊權）最小值。若無生成樹輸出 -1。

算法思路

邊按權值排序。枚舉最小邵 L，從 L 開始遞增 R，用並查集維護連通性。當圖連通時，當前苗條度 = w[R] - w[L]，更新答案，換下一個 L。
優化：內層循環可直接從上次 R 繼續（單調性），總複雜度 O(M² α(N))，M ≤ 4950 (N≤100) 可接受。

關鍵點

• 需處理多測試用例，以 0 0 結束。
• 圖可能不連通，檢查並查集最終集合數。
• 邊權 ≤ 10000，苗條度 ≤ 10000。