1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

題目描述： 給定一個加權無向圖，找出最小生成樹（MST）中的「關鍵邊」和「偽關鍵邊」。

• 關鍵邊：移除後 MST 權重增加或圖不連通的邊。
• 偽關鍵邊：存在於某個 MST 中但並非所有 MST 都包含的邊。

解題思路：

1. 先用 Kruskal 演算法求出 MST 的總權重 mstWeight。
2. 對每條邊判斷是否為關鍵邊：強制「排除」該邊後重新建 MST，若新 MST 權重增加或圖不連通，則為關鍵邊。
3. 對非關鍵邊判斷是否為偽關鍵邊：強制「包含」該邊後重新建 MST，若 MST 權重仍為 mstWeight，則該邊可以出現在某個 MST 中，為偽關鍵邊。

使用 Union-Find（DSU）實現 Kruskal 演算法，每次排除/包含一條邊重新跑。

時間複雜度：O(m^2 * alpha(n)) — 對每條邊執行一次 Kruskal（O(m * alpha(n))），共 m 條邊。alpha 為反阿克曼函數，幾乎為常數。

空間複雜度：O(n + m) — Union-Find 陣列 O(n)，邊陣列 O(m)。

Tarjan's Bridge + Cycle 分析：先建 MST，用 Tarjan 演算法找出橋邊（即關鍵邊）。對非關鍵邊，檢查替換後是否仍得到相同權重的 MST。時間 O(m * alpha(n))，但實作更複雜。

邊權分組 + 連通分量：將相同權重的邊分組，在每組內分析哪些邊是可互換的（偽關鍵）、哪些是必要的（關鍵）。時間可達 O(m * alpha(n))，是理論最優解但實作難度高。

1. 如果只需要找關鍵邊（不需要偽關鍵邊），有沒有更快的演算法？
2. 若圖的邊權全部相同，MST 的結構有什麼特殊性質？
3. 此問題與「最小生成樹的唯一性判斷」有什麼關聯？