解題說明
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 也不能),問題會如何改變?