684. Redundant Connection

Medium

Description

給定一個本應是樹的無向圖，多了一條邊形成環。圖以邊的列表 edges 給出（按輸入順序），找出移除後能使圖恢復為樹的那條多餘邊。若有多個答案，回傳最後出現的那條。

Example:

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

Intuition#

依序加入邊，第一條使得兩個已連通節點再次連接的邊就是多餘的。Union-Find 完美契合。

樹有 n 個節點和 n-1 條邊，多一條邊必然形成恰好一個環
依序處理邊，用 Union-Find 判斷兩端是否已在同一集合
若已在同一集合，加入這條邊會形成環，即為答案

Approaches#

1: DFS（每次加邊前檢查連通性）#

概念: 維護鄰接表，每加一條邊前用 DFS 檢查兩端是否已連通
時間複雜度: O(n^2)（每條邊做一次 DFS）
空間複雜度: O(n)

class Solution {
    fun findRedundantConnection(edges: Array<IntArray>): IntArray {
        val n = edges.size
        val graph = Array(n + 1) { mutableListOf<Int>() }

        fun hasPath(src: Int, dst: Int, visited: BooleanArray): Boolean {
            if (src == dst) return true
            visited[src] = true
            for (next in graph[src]) {
                if (!visited[next] && hasPath(next, dst, visited)) return true
            }
            return false
        }

        for ((u, v) in edges) {
            if (graph[u].isNotEmpty() && graph[v].isNotEmpty()) {
                val visited = BooleanArray(n + 1)
                if (hasPath(u, v, visited)) return intArrayOf(u, v)
            }
            graph[u].add(v)
            graph[v].add(u)
        }
        return intArrayOf()
    }
}

⭐2: Union-Find#

概念: 依序對每條邊做 union，若兩端已在同一集合，該邊即為答案
時間複雜度: O(n * α(n))（近似線性）
空間複雜度: O(n)

class Solution {
    private lateinit var parent: IntArray
    private lateinit var rank: IntArray

    fun findRedundantConnection(edges: Array<IntArray>): IntArray {
        val n = edges.size
        parent = IntArray(n + 1) { it }
        rank = IntArray(n + 1)

        for ((u, v) in edges) {
            if (!union(u, v)) return intArrayOf(u, v)
        }
        return intArrayOf()
    }

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

    private 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
    }
}

🔑 Takeaways#

Pattern: Union-Find 偵測環 – 加邊時兩端已同集合代表會形成環
關鍵技巧: Union-Find 的 union 回傳 false 表示兩者已連通，是經典的環偵測技巧