HardRating 2132
1579. Remove Max Number of Edges to Keep Graph Fully Traversable
union-findgraph
解題說明
Remove Max Number of Edges to Keep Graph Fully Traversable
題目描述：
給定 n 個節點和三種類型的邊：類型 1（僅 Alice 可用）、類型 2（僅 Bob 可用）、類型 3（兩人皆可用）。求最多可以移除多少條邊，同時保證 Alice 和 Bob 各自仍能遍歷所有節點。
解題思路： 使用兩個 Union-Find 結構分別追蹤 Alice 和 Bob 的連通性。
-
優先處理類型 3 的邊：因為共用邊同時服務兩人，性價比最高。對於每條類型 3 的邊，嘗試在兩個 UF 中合併。如果在至少一個 UF 中成功合併（即非冗餘），保留該邊；否則移除。
-
再處理類型 1 和類型 2 的邊：類型 1 只對 Alice 的 UF 操作，類型 2 只對 Bob 的 UF。同樣，冗餘邊可以移除。
-
最後驗證：如果 Alice 或 Bob 的 UF 連通分量數大於 1，表示無法全部遍歷，回傳 -1。
移除的邊數 = 總邊數 - 保留的邊數。
C++ 解法
複雜度分析
時間複雜度：O(E · α(n)) — 遍歷所有邊，每次 Union-Find 操作的攤銷時間為 α(n)（近似常數），其中 E 為邊的數量。
空間複雜度：O(n) — 兩個 Union-Find 各使用 O(n) 的 parent 和 rank 陣列。
虛擬碼
1. Create two Union-Find structures: alice_uf and bob_uf, each with n nodes
2. Set used = 0
3. First pass — process type 3 edges:
a. For each edge (3, u, v):
- Try to unite u, v in both alice_uf and bob_uf
- If either union was successful (not redundant), used++
4. Second pass — process type 1 and 2 edges:
a. For each edge (1, u, v): if alice_uf.unite(u, v) succeeds, used++
b. For each edge (2, u, v): if bob_uf.unite(u, v) succeeds, used++
5. If alice_uf or bob_uf has more than 1 component, return -1
6. Return total_edges - used其他解法
Kruskal 最小生成樹思路 O(E log E)：將邊按優先級排序（類型 3 優先），逐一加入生成森林。本質相同但排序增加了 O(E log E) 的開銷，不如直接兩趟掃描。
BFS/DFS 驗證法：分別為 Alice 和 Bob 建圖，使用 BFS/DFS 驗證連通性。但此法無法有效判斷哪些邊是冗餘的，需要額外的生成樹/圖邏輯。
延伸思考
- 如果有第三個人 Charlie（需要新的邊類型），如何擴展此演算法？
- 如果邊有權重，且要求保留的邊的總權重最小，問題變成什麼？
- 如何在動態加邊/刪邊的情境下維護此問題的答案？