解題說明
Process Restricted Friend Requests
題目描述： 有 n 個人和一組限制條件（restrictions），每個限制 [x, y] 表示 x 和 y 不能屬於同一個朋友群組。依序處理一系列交友請求（requests），每個請求 [u, v] 嘗試讓 u 和 v 成為朋友。若合併 u 和 v 的群組不會違反任何限制，則接受；否則拒絕。
解題思路： 使用 Union-Find（並查集）管理朋友群組。
-
對每個交友請求 [u, v]：
- 找到 u 和 v 的根節點 ru, rv。
- 若 ru == rv（已在同一群組），直接接受。
- 否則，檢查所有限制條件：對每個限制 [x, y]，若合併 ru 和 rv 後 x 和 y 會在同一群組，則拒絕。
- 具體檢查：find(x) 和 find(y) 是否分別等於 {ru, rv}（即 x 在 u 的群組且 y 在 v 的群組，或反過來）。
- 若無違反，執行 union(ru, rv)。
-
注意：不能先合併再檢查，因為一旦合併就無法撤銷（Union-Find 不支援 undo）。
C++ 解法
複雜度分析
時間複雜度：O(q * r * α(n)) — q 為請求數量，r 為限制數量，α(n) 為反阿克曼函數（Union-Find 操作的均攤複雜度）。
空間複雜度：O(n) — Union-Find 的 parent 和 rank 陣列。
虛擬碼
1. Initialize Union-Find with n elements.
2. For each request [u, v]:
a. ru = find(u), rv = find(v).
b. If ru == rv: accept (already friends).
c. Else, for each restriction [x, y]:
- rx = find(x), ry = find(y).
- If {rx, ry} == {ru, rv}: reject (would violate restriction).
d. If no violation found: union(ru, rv), accept.
e. Record result.
3. Return results.其他解法
-
可撤銷 Union-Find：先合併，然後檢查所有限制。若違反則撤銷合併。需要使用按秩合併（不做路徑壓縮）來支援撤銷。時間複雜度相同但常數因子較大。
-
圖著色 / 二分圖檢測：將限制視為「不能同色」的約束，每次請求等於嘗試合併兩個顏色群組。但本質上與 Union-Find 方法相同，只是換了一種思考角度。
延伸思考
- 若限制條件也是動態加入的（交友請求和限制交錯出現），如何修改演算法？
- 若需要支援「解除好友」操作（即分割群組），資料結構需要如何擴展？
- 若限制條件有傳遞性（x 和 y 不能同組，y 和 z 也不能，則 x 和 z 也不能），問題會如何改變？