HardRating 2572

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

union-findgraphsortingminimum-spanning-treestrongly-connected-component

在 LeetCode 上作答 ↗

解題說明

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

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

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

解題思路：

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

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

C++ 解法

複雜度分析

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

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

虛擬碼

1. Append original index to each edge, sort edges by weight
2. Compute mstWeight using standard Kruskal
3. For each edge i:
   a. Exclude edge i, run Kruskal:
      - If result > mstWeight or graph disconnected: edge is CRITICAL
   b. Else force-include edge i, run Kruskal:
      - If result == mstWeight: edge is PSEUDO-CRITICAL
4. Return [critical edges, pseudo-critical edges]

其他解法

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

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

延伸思考

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

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree — CaffeCode