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

Hard
Description

給定一個加權無向圖，找出所有最小生成樹（MST）中的關鍵邊和偽關鍵邊。關鍵邊是移除後會使 MST 權重增加的邊；偽關鍵邊是可以出現在某些 MST 中但不是所有 MST 都需要的邊。

Example:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]] Output: [[0,1],[2,3,4,5]]

Intuition#

對每條邊測試：排除後 MST 增加 -> 關鍵邊；強制包含後 MST 不變 -> 偽關鍵邊。

  • 先用 Kruskal 求出 MST 的基準權重
  • 對每條邊：
    • 排除該邊後重新求 MST，若權重增加或無法形成 MST -> 關鍵邊
    • 非關鍵邊，強制包含該邊後求 MST，若權重等於基準 -> 偽關鍵邊

Approaches#

⭐1: Kruskal + 逐邊測試#

  • 概念: 基準 MST + 對每條邊做排除/強制測試
  • 時間複雜度: O(E^2 * α(V))
  • 空間複雜度: O(V + E)
class Solution {
    fun findCriticalAndPseudoCriticalEdges(n: Int, edges: Array<IntArray>): List<List<Int>> {
        // 記錄原始索引
        val indexed = Array(edges.size) { i -> intArrayOf(edges[i][0], edges[i][1], edges[i][2], i) }
        indexed.sortBy { it[2] }

        val baseMST = kruskal(n, indexed, -1, -1)
        val critical = mutableListOf<Int>()
        val pseudo = mutableListOf<Int>()

        for (i in indexed.indices) {
            // 排除邊 i
            val without = kruskal(n, indexed, i, -1)
            if (without > baseMST) {
                critical.add(indexed[i][3])
            } else {
                // 強制包含邊 i
                val with = kruskal(n, indexed, -1, i)
                if (with == baseMST) {
                    pseudo.add(indexed[i][3])
                }
            }
        }

        return listOf(critical, pseudo)
    }

    private fun kruskal(n: Int, edges: Array<IntArray>, exclude: Int, include: Int): Int {
        val parent = IntArray(n) { it }
        val rank = IntArray(n)
        var weight = 0
        var edgeCount = 0

        fun find(x: Int): Int {
            if (parent[x] != x) parent[x] = find(parent[x])
            return parent[x]
        }

        fun union(x: Int, y: Int): Boolean {
            val px = find(x)
            val py = find(y)
            if (px == py) return false
            if (rank[px] < rank[py]) parent[px] = py
            else if (rank[px] > rank[py]) parent[py] = px
            else { parent[py] = px; rank[px]++ }
            return true
        }

        // 強制包含
        if (include != -1) {
            val (u, v, w) = edges[include]
            union(u, v)
            weight += w
            edgeCount++
        }

        for (i in edges.indices) {
            if (i == exclude || i == include) continue
            val (u, v, w) = edges[i]
            if (union(u, v)) {
                weight += w
                edgeCount++
            }
        }

        return if (edgeCount == n - 1) weight else Int.MAX_VALUE
    }
}

2: 簡化版（相同邏輯）#

  • 概念: 將 Union-Find 封裝為類別，程式碼更清晰
  • 時間複雜度: O(E^2 * α(V))
  • 空間複雜度: O(V + E)
class Solution {
    fun findCriticalAndPseudoCriticalEdges(n: Int, edges: Array<IntArray>): List<List<Int>> {
        val m = edges.size
        val idx = (0 until m).sortedBy { edges[it][2] }

        fun mst(skip: Int, pick: Int): Int {
            val uf = IntArray(n) { it }
            var w = 0; var cnt = 0

            fun find(x: Int): Int { var a = x; while (uf[a] != a) { uf[a] = uf[uf[a]]; a = uf[a] }; return a }
            fun unite(x: Int, y: Int): Boolean { val a = find(x); val b = find(y); if (a == b) return false; uf[a] = b; return true }

            if (pick >= 0) { unite(edges[pick][0], edges[pick][1]); w += edges[pick][2]; cnt++ }
            for (i in idx) {
                if (i == skip) continue
                if (unite(edges[i][0], edges[i][1])) { w += edges[i][2]; cnt++ }
            }
            return if (cnt == n - 1) w else Int.MAX_VALUE
        }

        val base = mst(-1, -1)
        val critical = mutableListOf<Int>()
        val pseudo = mutableListOf<Int>()

        for (i in 0 until m) {
            if (mst(i, -1) > base) critical.add(i)
            else if (mst(-1, i) == base) pseudo.add(i)
        }
        return listOf(critical, pseudo)
    }
}

🔑 Takeaways#

  • Pattern: MST 邊分類 – 排除/強制測試法
  • 關鍵技巧: 排除一條邊後 MST 權重增加或不連通 -> 關鍵邊；非關鍵邊中強制包含後 MST 權重不變 -> 偽關鍵邊；時間複雜度 O(E^2) 在 E 較小時可接受