HardRating 1897
685. Redundant Connection II
depth-first-searchbreadth-first-searchunion-findgraph
解題說明
Redundant Connection II
題目描述:給定一個有向圖,原本是以 n 個節點(1 到 n)組成的有根樹(rooted tree),但多了一條額外的有向邊導致圖變得不合法。找出並回傳這條多餘的邊。若有多個答案,回傳輸入陣列中最後出現的那條邊。
解題思路:
有效的有根樹需要滿足兩個條件:
- 每個非根節點的入度恰好為 1。
- 圖中沒有環。
多加一條邊可能破壞上述其中一個或兩個條件,因此分三種情況討論:
- 情況一:沒有入度為 2 的節點 — 多餘邊製造了環,但每個節點入度仍為 1。此時直接用 Union-Find 找造成環的那條邊(與無向版 LC 684 相同)。
- 情況二:有入度為 2 的節點(且無環) — 找到入度為 2 的節點,它有兩條入邊
cand1和cand2,移除其中較後出現的那條(cand2)即可。 - 情況三:有入度為 2 的節點(且有環) — 入度為 2 的節點的兩條入邊中,必定是其中一條導致了環。用 Union-Find 跳過
cand2,若仍然有環,則答案是cand1;否則答案是cand2。
實作步驟:
- 第一輪掃描邊,記錄每個節點的入度;若節點 v 入度為 2,記錄
cand1(先出現)和cand2(後出現)。 - 第二輪用 Union-Find 處理所有邊(跳過
cand2若存在):- 若發現環,根據是否有
cand2決定回傳cand1或環上那條邊。
- 若發現環,根據是否有
- 若沒有環,回傳
cand2。
C++ 解法
複雜度分析
時間複雜度:O(n · α(n)) — 掃描邊兩次共 O(n),Union-Find 的 n 次操作均攤 O(α(n)),整體接近 O(n)。
空間複雜度:O(n) — parent、rank、indegree 陣列各 O(n)。
虛擬碼
1. Scan edges, track indegree[] for each node
- If indegree[v] == 2: record cand1 (earlier edge to v) and cand2 (later edge to v)
2. Initialize Union-Find with n nodes
3. For each edge e in edges:
a. If e == cand2: skip
b. Attempt unite(e[0], e[1])
c. If unite returns false (cycle):
- If cand1 is empty: return e // Case 1: no double-indegree
- Else: return cand1 // Case 3: cand1 causes cycle
4. No cycle encountered => return cand2 // Case 2: cand2 is redundant其他解法
DFS 找環 O(n):不用 Union-Find,直接對有向圖做 DFS 找環並記錄環上的邊,再結合入度分析決定答案。優點是概念清晰,缺點是 DFS 需要維護訪問狀態(visited/in-stack),程式碼比 Union-Find 版複雜,且需要小心處理有向環的識別。
拓撲排序輔助 O(n):先用拓撲排序找到使圖不合法的節點,再枚舉相關邊。優點是可以同時處理入度異常與環的問題,缺點是需要多次掃描,不如 Union-Find 方法直接。
暴力枚舉 O(n²):逐一嘗試移除每條邊,檢查剩餘圖是否為合法有根樹。優點是實作最簡單,缺點是時間複雜度過高,n 達 1000 時共需 O(n²) 次驗證,難以通過時間限制。
延伸思考
- 無向圖版本(LC 684)可直接用 Union-Find 找環,有向圖版本需要額外考慮入度,請問有向圖的解法為何不能直接套用無向版?
- 若圖中可能有多個節點入度為 2(即多條多餘邊),演算法需要如何修改?
- 題目保證答案唯一,若不保證唯一,「回傳輸入中最後出現的邊」這個條件如何在三種情況中分別體現?