給定一個本應是樹的無向圖，多了一條邊形成環。圖以邊的列表
edges給出（按輸入順序），找出移除後能使圖恢復為樹的那條多餘邊。若有多個答案，回傳最後出現的那條。
Example:
Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3]
Intuition
TIP
依序加入邊，第一條使得兩個已連通節點再次連接的邊就是多餘的。Union-Find 完美契合。
- 樹有 n 個節點和 n-1 條邊，多一條邊必然形成恰好一個環
- 依序處理邊，用 Union-Find 判斷兩端是否已在同一集合
- 若已在同一集合，加入這條邊會形成環，即為答案
Approaches
1. DFS (check connectivity before each edge) — O(n^2) / O(n)
- Idea: 維護鄰接表，每加一條邊前用 DFS 檢查兩端是否已連通
- Time:
O(n^2)（每條邊做一次 DFS） - Space:
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 — O(n * α(n)) / O(n)
- Idea: 依序對每條邊做 union，若兩端已在同一集合，該邊即為答案
- Time:
O(n * α(n))（近似線性） - Space:
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 偵測環 — 加邊時兩端已同集合代表會形成環
- Key trick: Union-Find 的
union回傳false表示兩者已連通，是經典的環偵測技巧