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（即多條多餘邊），演算法需要如何修改？
- 題目保證答案唯一，若不保證唯一，「回傳輸入中最後出現的邊」這個條件如何在三種情況中分別體現？