1579. Remove Max Number of Edges to Keep Graph Fully Traversable

Hard
Description

有 n 個節點和三種邊：type 1 只有 Alice 能用，type 2 只有 Bob 能用，type 3 雙方都能用。求最多能移除多少條邊，使得 Alice 和 Bob 仍然都能遍歷整張圖。若無法同時滿足，回傳 -1。

Example:

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

Intuition#

貪心：優先使用 type 3（共用邊），再分別用 type 1 和 type 2 補充。

  • type 3 的邊對 Alice 和 Bob 都有用，效益最大
  • 優先加入 type 3 邊，形成初始連通結構
  • 再分別為 Alice 加 type 1 邊，為 Bob 加 type 2 邊
  • 未被使用的邊就是可以移除的

Approaches#

⭐1: 雙 Union-Find + 貪心#

  • 概念: 先處理 type 3 邊，再分別處理 type 1 和 type 2。用兩套 Union-Find 分別追蹤 Alice 和 Bob 的連通性。
  • 時間複雜度: O(E * α(V))
  • 空間複雜度: O(V)
class Solution {
    fun maxNumEdgesToRemove(n: Int, edges: Array<IntArray>): Int {
        val alice = UnionFind(n)
        val bob = UnionFind(n)
        var usedEdges = 0

        // 優先處理 type 3（雙方共用）
        for ((type, u, v) in edges) {
            if (type == 3) {
                val usedA = alice.union(u, v)
                val usedB = bob.union(u, v)
                if (usedA || usedB) usedEdges++
            }
        }

        // 處理 type 1（Alice 專用）
        for ((type, u, v) in edges) {
            if (type == 1) {
                if (alice.union(u, v)) usedEdges++
            }
        }

        // 處理 type 2（Bob 專用）
        for ((type, u, v) in edges) {
            if (type == 2) {
                if (bob.union(u, v)) usedEdges++
            }
        }

        // 檢查兩者是否都連通
        if (alice.components != 1 || bob.components != 1) return -1

        return edges.size - usedEdges
    }

    class UnionFind(n: Int) {
        val parent = IntArray(n + 1) { it }
        val rank = IntArray(n + 1)
        var components = n

        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]++ }
            components--
            return true
        }
    }
}

2: 相同邏輯的另一種寫法#

  • 概念: 將邊按 type 分組，依序處理
  • 時間複雜度: O(E * α(V))
  • 空間複雜度: O(V + E)
class Solution {
    fun maxNumEdgesToRemove(n: Int, edges: Array<IntArray>): Int {
        val parentA = IntArray(n + 1) { it }
        val parentB = IntArray(n + 1) { it }
        val rankA = IntArray(n + 1)
        val rankB = IntArray(n + 1)
        var removed = 0

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

        fun union(parent: IntArray, rank: IntArray, x: Int, y: Int): Boolean {
            val px = find(parent, x)
            val py = find(parent, 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
        }

        // type 3 先處理
        for ((type, u, v) in edges) {
            if (type == 3) {
                val a = union(parentA, rankA, u, v)
                val b = union(parentB, rankB, u, v)
                if (!a && !b) removed++
            }
        }

        for ((type, u, v) in edges) {
            when (type) {
                1 -> if (!union(parentA, rankA, u, v)) removed++
                2 -> if (!union(parentB, rankB, u, v)) removed++
            }
        }

        val compA = (1..n).map { find(parentA, it) }.distinct().size
        val compB = (1..n).map { find(parentB, it) }.distinct().size
        return if (compA == 1 && compB == 1) removed else -1
    }
}

🔑 Takeaways#

  • Pattern: 雙 Union-Find + 貪心 – 多人共用邊的最大化移除問題
  • 關鍵技巧: 優先處理 type 3 邊（效用最大），冗餘邊可以移除；type 3 邊即使只對一方有效也應保留